依据《算法导论》(第二版中文版,机械工业出版社出版)第539页的算法来实现,速度非常快。即使是对非常大的参数也是如此
#include
using namespace std;
int f(int a,int b,int n);
int main()
{
cout< return 0;
}
int f(int a,int b,int n)
{
if(a<0||b<0||n<0)return -1;
int binary[32];
int index=0;
while(b)
{
if(b&1)
{
binary[index]=1;
}
else
{
binary[index]=0;
}
index++;
b>>=1;
}
index--;
int result=1;
while(index>=0)
{
result=(result*result)%n;
if(binary[index])
{
result=(result*a)%n;
}
index--;
}
return result;
}