 //(a^b)%n
#include<iostream>
//这里用的是什么方法呢?
int modExp(int a,int b,int n)
   {
 int t=1,y=a;
while(b)
  {
if(b%2==1)t=t*y%n;
y=y*y%n;
b=b/2;
 }
return t;
 }
//常规
int modexp(int a,int b,int n)
{
int t=1;
for(int i=0;i<b;i++)t=t*a;
return t%n;
}
int main(void)
{
int a=0,b=0,n=0;
std::cin>>a>>b>>n;
std::cout<<modExp(a,b,n)<<std::endl;
std::cout<<modexp(a,b,n)<<std::endl;
return 0;
}
谁能给我讲讲它这个方法是什么数学原理呢? //第二个函数仅为测试正确性设置,不考虑溢出问题
|