SFQRM
SFQRM
2015-03-29 09:16
采纳率: 25%
浏览 4.7k
已采纳

一道关于大数幂运算的题目,c语言实现

题目描述
幂运算是常见的数学运算之一,其原理是用同一个数相乘多次,但是有的时候当幂指数特别大的时候,这样的运算就太浪费时间。请大家学会在幂中加特技,让幂运算的效率提高到可以接受的程度。
输入:
第一个行一个整数T,表示有T组数据
每组数据,输入x,y 求x的y次幂 (2≤ x ,y≤10^9)
输出:
每组数据输出一个整数,表示幂运算对1000000007取模后的结果
样例输入:
2
2 4
2 100000000
样例输出:
16
494499948
我的代码总是超时,求好方法!!谢谢!!

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

9条回答 默认 最新

  • caozhy
    已采纳

    不知道你怎么算的
    我们知道
    a^m可以视作a^p*a^q(p+q=m)
    而如果p=m,显然,我们只要算了a^p,就可以再平方下就是最后的结果了。
    因此最简单的做法就是,将指数转化成2的幂相加的结果,这相当于二进制计算,比如100000000
    就是101111101011110000100000000(2)
    那么就是256+8192+16384+32768+65536+262144+1048576+...
    然后我们分别计算N的这些次方的幂,别忘了,我们可以通过平方翻倍很快算出来。
    最后再把结果相乘。

    点赞 评论
  • caozhy

    如果你愿意先采纳几个问题的答案,可以写一些代码给你

    点赞 评论
  • caozhy

    好的,不过你的测试用例不对,2^100000000不可能只有那么一点

    点赞 评论
  • cloudy07
    cloudy07 2015-03-29 12:17

    代码贴出来了吗?

    点赞 评论
  • caozhy
     #include <iostream>
    #define QTMAX 40
    
    using namespace std;
    
    int lenqt(int qt[])
    {
        for (int i = QTMAX - 1; i >= 0; i--)
        {
            if (qt[i]) return i + 1;
        }
        return 0;
    }
    
    int main()
    {
        int x = 2;
        int y = 17;
        int yy = y;
        int qt[QTMAX];
        double qr[QTMAX];
        for (int i = 0 ; i < QTMAX; i++)  qt[i] = 0;
        int idx = 0;
        while (yy > 0)
        {
            qt[idx++] = yy % 2;
            yy /= 2;
        }
        double xx = (double)x;
        qr[0] = xx;
        for (int i = 1; i < lenqt(qt); i++)
        {
            qr[i] = qr[i - 1] * qr[i - 1];
            cout << qr[i] << endl;
        }
        double r = 1.0;
        for (int i = 0; i < lenqt(qt); i++)
        {
            int j = lenqt(qt) - i - 1;        
            if (qt[i])
            {
                cout << j << " " << qr[j] << endl;
                r *= qr[j];
            }
        }
        cout << r << endl;
    }
    

    http://codepad.org/0jKh2yWa

    点赞 评论
  • caozhy

    有点bug,稍后帮你搞定

    点赞 评论
  • caozhy

    之前的程序有点小错

    这是修正后的程序

    其中slowpow是普通版本,mypow是加速版本,你体会下

     // ConsoleApplication1.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    
    #include <iostream>
    #define QTMAX 40
    
    using namespace std;
    
    int lenqt(int qt[])
    {
        for (int i = QTMAX - 1; i >= 0; i--)
        {
            if (qt[i]) return i + 1;
        }
        return 0;
    }
    
    double mypow(int x, int y)
    {
        int yy = y;
        int qt[QTMAX];
        double qr[QTMAX];
        for (int i = 0; i < QTMAX; i++)  qt[i] = 0;
        int idx = 0;
        while (yy > 0)
        {
            qt[idx++] = yy % 2;
            yy /= 2;
        }
        double xx = (double)x;
        qr[0] = xx;
        for (int i = 1; i < lenqt(qt); i++)
        {
            qr[i] = qr[i - 1] * qr[i - 1];
        }
        double r = 1.0;
        for (int i = 0; i < lenqt(qt); i++)
        {
            if (qt[i])
            {
                r *= qr[i];
            }
        }
        return r;
    }
    
    double slowpow(int x, int y)
    {
        double r = x;
        for (int i = 1; i < y; i++)
            r *= (double)x;
        return r;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
        cout << mypow(1, 2100000000) << endl;
        cout << slowpow(1, 2100000000) << endl;
        return 0;
    }
    
    
    
    点赞 评论
  • u012436960
    u012436960 2015-03-30 09:07
    #include<stdio.h>
    #define MOD 1000000007
    // a^x
    unsigned long long pow(unsigned long long a,
                           unsigned long long x)
    {
        unsigned long long result=1;
        a%=MOD;
        while(x)
        {
            if(x&1)
                result=(result*a)%MOD;
            a=(a*a)%MOD;
            x>>=1;
        }
        return result;
    }
    
    int main()
    {
        unsigned long long a,x;
        scanf("%llu%llu",&a,&x);
        printf("%llu\n",pow(a,x));
        return 0;
    }
    

    试试这个

    点赞 评论
  • caozhy
    点赞 评论

相关推荐