题意
求 $a\times b\bmod p$ 。
分析
快速乘,一般是在模数太大导致直接乘会爆long long
的地方使用,龟速快速计算两个数在模意义下的乘积,复杂度 $O(\log b)$ 。具体原理和快速幂差不多,就是把乘数拆成二进制分解。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,mod;
ll mul(ll a,ll p){
ll res=0;
while(p){
if(p&1)res=(res+a)%mod;
p>>=1;
a=(a+a)%mod;
}
return res;
}
int main(){
scanf("%lld%lld%lld",&a,&b,&mod);
printf("%lld\n",mul(a,b));
return 0;
}