快速幂
第一次写的代码：
#include <iostream> using namespace std; int main(){ int a,b,p; cin>>a>>b>>p; int res=1%p; while(b){ if(b&1) res=res*1ll*a%p; a=a*a*1ll%p; //这个代码这个地方会使得我们有的数据过不去 b>>=1; } cout<<res; return 0; }
正确的代码模板如下，重要的快速幂的部分将他加粗：
#include <iostream> using namespace std; int main(){ int a,b,p; cin>>a>>b>>p; int res=1%p; while(b){ if(b&1) res=res*1ll*a%p; a=a*1ll*a%p; b>>=1; } cout<<res; return 0; }
在第一次的代码中我们发现会过不去数据样例，如下：
问题出在代码段
a=a*a*1ll%p; //这个代码这个地方会使得我们有的数据过不去
给的数据是123348976 ，a本来就是int类型 （1e8），a*a就已经很大了，有1e16以上了。。。
2的31次方========2,147,483,648
int的数据的最大值为2,147,483,648-1 在C*1e9次方的范围
所以a*a就是超出了范围，就会数据溢出，就得不到正确的数据 。。。
正确的代码段应该是
a=a*1ll*a%p;
这样的话就先把a*a转化为了long long类型，就不会数据溢出。。
在这里强调一下
*1ll是一种简单的写法，可以简化代码，写起来更快。
当然我们也可以采用 显而易见的强制类型转换
写成
a=(long long) a*a%p;
也是可以AC这些数据的。。。。