我们可以发现，如果将a和b直接进行相乘的话，那肯定会爆long long。当然，python选手自动忽略。那么，我们可以这样思考，对于任意一个整数，我们都可以用二进制进行表示，也就是用二进制进行拆分，比如：b=2^n+2^(n-1)+...+2^3+2^0.所以我们就可以把ab=a2^n+a2^(n-1)+...+a2^3+a2^0,这样，我们就是分别进行一个快速幂，然后累加到答案即可。其实可以把b想象成一个01二进制串，然后，我们可以通过将b不断进行向右进行移位的方式进行求解，其实就是和快速幂非递归的思路差不多。
#include<iostream>
using namespace std;
typedef long long ll;
ll a,b,p;
int main(){
cin>>a>>b>>p;
ll ans=0;
while(b){ //将b想象成01串
if(b&1) ans=(ans+a)%p; //如果这一位为1,那么它就对结果有权，计算出累加到答案即可
a=a*2%p; //这里可以确保a不会爆longlong
b>>=1; //不断将b进行右移位
}
cout<<ans<<endl;
return 0;
}
//python一步解决
a=int(input())
b=int(input())
p=int(input())
ans=a*b
ans%=p
print(a*b%p)
京公网安备 11010502036488号