 //(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;
}
誰能給我講講它這個方法是什么數學原理呢? //第二個函數僅為測試正確性設置,不考慮溢出問題
|