题目描述
求 aa 乘 bb 对 pp 取模的值。
算法:龟速乘
时间复杂度:$logN$
需要注意
(1)实现两个数相乘,时间复杂度比O(1)还大,是log(n)
(2)优势在于:不用写高精度乘法,在时间复杂度允许的范围内,可以节省代码复杂度
C++代码
#include<iostream>
using namespace std;
typedef long long LL;
LL qadd(LL a,LL b,LL p)
{
LL res=0;
while(b){
if(b&1)res=(res+a)%p;
a=(a+a)%p;
b>>=1;
}
return res;
}
int main()
{
LL a,b,p;
scanf("%lld%lld%lld",&a,&b,&p);
cout<<qadd(a,b,p)<<endl;
return 0;
}