//(a^b)%n
#include<iostream>
//这里用的是什么方法呢?
int modExp(int a,int b,int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int t=1,y=a;
while(b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int t=1;
for(int i=0;i<b;i++)t=t*a;
return t%n;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main(void)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
谁能给我讲讲它这个方法是什么数学原理呢? //第二个函数仅为测试正确性设置,不考虑溢出问题
|