当前位置 博文首页 > weixin_30267785的博客:模板—慢速乘

    weixin_30267785的博客:模板—慢速乘

    作者:[db:作者] 时间:2021-09-04 09:17

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

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #define LL long long
    using 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<<ans<<endl;
    }
    
    cs