快速幂思想
(a*b)%c = ((a%c)(b%c)) % c;
(a+b)%c = ((a%c) + (b%c)) % c;
这道题用这个,把a*b看作b个a,把b看做二进制数
一个样例
3*4%5
3*(100(二进制))%5
#include <iostream>
typedef unsigned long long LL;
LL qmi(LL a,LL b,LL p)
{
LL res=0;
while(b)
{
if(b&1)res=(res+a)%p;
b>>=1;
a=a*2%p;
}
return res;
}
int main()
{
LL a,b,p;
scanf("%lld%lld%lld",&a,&b,&p);
LL ans = qmi(a,b,p);
printf("%lld",ans);
return 0;
}