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

问题描述：

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

答

不知道你怎么算的
我们知道
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的这些次方的幂，别忘了，我们可以通过平方翻倍很快算出来。
最后再把结果相乘。

答

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

答

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

答

代码贴出来了吗？

答

 #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

答

有点bug，稍后帮你搞定

答

之前的程序有点小错

这是修正后的程序

其中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;
}

答

#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;
}

试试这个

答

http://bbs.csdn.net/topics/391006597

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

相关推荐