快速乘法模板

　

乘法

快速乘法使用二进制将乘法转化为加法，既加快可以加快运算速度，又可以防止直接相乘之后溢出

简单的写法：

ll quickMul(ll a,ll b,ll mod)
{
    ll res=0;
    while(b){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}

更快更高效的写法：

ll mul(ll a,ll b,ll mod)
{
    a%=mod;
    b%=mod;
    ll res=0;
    while(b){
        if(b&1){
            res+=a;
            if(res>=mod)
                res-=mod;
        }
        b>>=1;
        a<<=1;
        if(a>=mod)  a-=mod;
    }
    return res;
}

利用快速乘法优化的快速幂：

ll mul(ll a,ll b,ll mod)
{
    a%=mod;
    b%=mod;
    ll res=0;
    while(b){
        if(b&1){
        //printf("%lld %lld %lld\n",a,b,res);
            res+=a;
            if(res>=mod)
                res-=mod;
        }
        b>>=1;
        a<<=1;
        if(a>=mod)  a-=mod;
    }
    return res;
}
ll quickPow(ll a,ll b,ll m)
{
    ll res=1;
    while(b){
        if(b&1)
        res=mul(res,a,m);
        a=mul(a,a,m);
        b>>=1;
    }
    return res;
}

相关阅读

快速乘方

问题描述： 求A^k mod B 输入： 包括三个正整数A，B，k ，其中1<=A<B<=10,000  ,1<=k<=2,000,000,000 输出： 一个整数表示A^k mod B的值 样

优化网站关键字的快速自然排名方法

一个网站的关键词排名最快的应该是做竞争推广，但是这种方式需要的成本会比较高。而自然排名的关键词优化则是相对成本比较少的。不

基于quartz的任务调度插件封装，快速集成项目

simple-quartz-tasks基于quartz的任务调度插件，引入到spring项目中实现任务信息装载接口即可使用，依赖于redis的订阅完成对任务的立

带你从零开始，快速学会 Matlab GUI

本文来自作者 木木小迷哥 在 GitChat 上分享「Matlab GUI 零基础学员快速入门」，「阅读原文」查看交流实录「文末高能」编辑

大白NB-IOT 移远BC28模块模组快速入门 （教您10分钟打通

今天大白来为大家详细介绍我们的大白BC28评估板的快速入门指南。 文末有彩蛋！！！