[Acwing] 算法提高课汇总六 基础算法

位运算 64位整数乘法

题意 : 给定 a , b ( 1 0 18 ) a,b(10^{18}) a,b(1018),询问 a ∗ b % p a*b\%p a∗b%p的值

思路 : 我们可以采用类似与快速幂的想法

b = 2 1 + 2 2 . . . . . + 2 n b =2^1+2^2.....+2^n b=21+22.....+2n a ∗ b = a ∗ 2 1 + a ∗ 2 2 . . . . + a ∗ 2 n a*b=a*2^1+a*2^2....+a*2^n a∗b=a∗21+a∗22....+a∗2n

因此我们只需要类似于快速幂的处理方法即可,在奇数的时候进行计算贡献

code :

ll qmi(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;
	
}

void solve(){
	ll a,b,p;cin>>a>>b>>p;
	cout