快速乘

快速乘

两个大数a，b（可能会超定义的类型的范围）相乘对mod求余
显然直接乘是不可能的
所以我们把b转成二进制
例 a=11,b=11
b的二进制是1011
所以a*b=a * (1 * 2³ +0 * 2² + 1 * 2¹+1 * 2⁰)=a * (8+2+1)=121;
下面是代码

#include <stdio.h>
int fast_mul(int a,int b,int mod)
{
    int ans=0;//ans最终求余的结果
    while(b)
    {
        if(b%2)
            ans=(ans%mod+a%mod)%mod;
        a=(a%mod+a%mod)%mod;
        b/=2;
    }
    return ans%mod;//返回a*b%mod的结果
}
int main()
{
    int a,b,mod;
    while(~scanf("%d,%d,%d",&a,&b,&mod))
        printf("%d
",fast_mul(a,b,mod));
    return 0;
}