有道难题练习题

时间：2010-05-25 来源：华南理工大学

描述

计算a的b次方对9907取模的值。

输入

第一行有一个正整数T，表示有T组测试数据。
接下来T行，每行是一组测试数据，包含两个整数a和b。
其中T<=10000, 0 <=a,b < 2^31。

输出

有T行，依次输出每组数据的结果。

样例输入

1 2

2 3

3 4

样例输出

解题思路

首先将a对9907取模，开个数据d[i]表示 a^(2^i)。先计算d[i]，然后按b的二进制表示求结果，比如b=3=011，结果为d[0]*d[1]对9907取模，b=8=100，结果为d[2]mod 9907。

代码

#include<iostream>
using namespace std;
int d[33];
int main()
{
    int T,a,b;
    int i,j;
    scanf("%d",&T);
    for(i=0;i<T;++i)
    {
        scanf("%d%d",&a,&b);
        a=a%9907;
        int k=0;
        d[0]=a;
        for(j=1;j<=32;++j)
        {
            d[j]=(d[j-1]*d[j-1])%9907;
        }
        int res=1;
        k=0;
        while(b)
        {
            if(b%2)
            {
                res*=d[k];
                res%=9907;
            }
            b=b>>1;
            k++;
        }
        printf("%d\n",res);

    }
    return 0;
}