用于模数很大直接乘会爆longlong的情况。

#include
     
      #include
      
       #include
       
        #define LL long longusing namespace std;LL a,b,p;LL mull(LL a,LL b,LL p){	LL res=0;	while(b)	{		if(b&1)res=(res+a)%p;		a=(a+a)%p;		b=b>>1;	}	return res;}signed main(){	cin>>a>>b>>p;	LL ans=mull(a,b,p);	cout<
        
         <
        
       
      
     

好处是只要a,b在long long内，无论它们乘起来多大，都可以做。

劣势是时间复杂度是log(b)的，比起正常乘法来太慢了。

其实有O（1）的方法， 只适用于a*b没有超过long long太多的情况（即a,b并不算大，大概均在10^12左右）

设一个常数t。

令x1=a/t，x2=a%t

    y1=b/t，y2=b%t

显然a*b=(x1*t+x2)*(y1*t+y2)=x1*y1*t*t+x1*y2*t+x2*y1*t+x2*y2。但是感觉并不如慢速乘好用……