计算h个a的b次幂的和,然后对m取余。。。直接pow是不行的
查找《算法导论》后得到算法,太牛逼了
先将b转换成2进制,存放在一个数组bin里面
d<-1
for i=0 to k-1 k为bin中存放的个数
d<-d*d mod m
if bin[i]==1
d<-d*a mod m
以上是a的b次幂的算法
#include <iostream>
#include <string>
#include <vector>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
vector<int> bin,rev;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void GetBinary(long long int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
long long int temp;
while (b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
bin.push_back(b%2);
b=b/2;
}
for (int i=bin.size()-1;i>=0;i--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rev.push_back(bin[i]);
}
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int num;
long long int d,sum,h,m,a,b;
scanf("%d",&num);
while (num--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
sum=0;
scanf("%lld",&m);
scanf("%lld",&h);
while (h--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%lld %lld",&a,&b);
bin.clear();rev.clear();
GetBinary(b);
d=1;
for(int index=0;index<(size_t)rev.size();index++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
d=(d*d)%m;
if (rev[index]==1)
d=(d*a)%m;
}
sum+=d;
}
printf("%lld\n",sum%m);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)