快速乘 + 快速幂 + 取模

忘是亡心i 2022-06-08 09:38 134阅读 0赞

**& 与运算**

9&5可写算式如下：  
00001001 (9的二进制补码)&00000101 (5的二进制补码) 00000001 (1的二进制补码)  
**9&5=1**

//快速乘法 
    int qmul_num(int a, int b) {
        int ans = 0;
        while(b) {
            if(b & 1) ans += a;
            b >>= 1;
            a <<= 1;
        }
        return ans;
    }

//快速乘法 + 取模 
    int qmul_mod(int a, int b, int mod) {
        int ans = 0;
        while(b) {
            if((b %= mod) & 1) ans += a %= mod;
            b >>= 1;
            a <<= 1;
        }
        return ans % mod;
    }

//快速幂 
    int pow_num(int a, int n) {
        if(a == 0) return 0;
        int ans = 1;
        while(n) {
            if(n & 1) ans *= a;
            n >>= 1;
            a *= a;
        }
        return ans;
    }

//快速幂 + 取模
    int pow_mod(int a, int n, int mod) {
        if(!a) return 0;
        int ans = 1;
        while(n) {
            if(n & 1) ans = (ans%mod) * (a%mod);
            n >>= 1;
            a *= a %= mod;
        }
        return ans % mod;
    }

//快速幂 + 取模 （简化）
    int pow_mod(int a, int n, int mod) {
        if(!a) return 0;
        int ans = 1;
        while(n) {
            if(n & 1) ans *= a %= mod;
            n >>= 1;
            a *= a;
        }
        return ans % mod;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，134人围观）

还没有评论，来说两句吧...

相关阅读

相关快速计算a的n次方（快速幂&&运算取模规则）

使用pow(a,n)计算 a n a^n an，时间复杂度是 O ( n ) O(n) O(n) （返回值是int，使用long就收可能出问题）使用快速幂可以把时间复杂

骑猪看日落/ 2022年11月13日 14:28/ 0 赞/ 231 阅读

相关 51Nod 1013 3的幂的和（快速幂取模+逆元）

51Nod 1013 3的幂的和（快速幂取模+逆元）：[http://www.51nod.com/onlineJudge/questionCode.html\!problem

深碍√TFBOYSˉ_/ 2022年09月25日 08:28/ 0 赞/ 117 阅读

相关快速幂取模及其应用

快速幂取模用法：用于求解 a 的 b 次方，而b是一个非常大的数，用O（n）的复杂度会超时。那么就需要这个算法，注意它不但可以对数求次幂，而且可用于矩阵快速幂。

小灰灰/ 2022年08月26日 04:54/ 0 赞/ 130 阅读

相关快速幂取模算法模板

在Miller Rabbin测试素数，就用到了快速幂取模的思想。这里总结下。求a^b%c（这就是著名的RSA公钥的加密方法），当a,b很大时，直接求解这个问题不太可能

分手后的思念是犯贱/ 2022年08月09日 13:46/ 0 赞/ 132 阅读

相关【算法】求n的m次方（快速幂取模）

题目求n的m次方，n，m均为自然数。解析看似简单的题目，但是要想写的高效还不是那么容易想出来。实现 unsigned int power(

以你之姓@/ 2022年08月09日 06:45/ 0 赞/ 209 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 270 阅读

相关快速乘 + 快速幂 + 取模

& 与运算 9&5可写算式如下： 00001001 (9的二进制补码)&00000101 (5的二进制补码) 00000001 (1的二进制补码) 9&5=1

忘是亡心i/ 2022年06月08日 09:38/ 0 赞/ 135 阅读

相关 UVa11582 - Colossal Fibonacci Numbers! （快速幂取模）

输入两个非负数 a，b，和正整数n，计算f（a^b）除以n的余数； f（i+2） = f（i+1） + f（i）; 函数f里是一个斐波那契数，所以需要打表，但是由于数

阳光穿透心脏的1/2处/ 2022年06月08日 09:28/ 0 赞/ 143 阅读

相关汉诺塔（快速幂取模）

汉诺塔（一）时间限制：1000 ms | 内存限制：65535 KB 难度：3 描述在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣

Bertha 。/ 2022年06月03日 22:59/ 0 赞/ 386 阅读

相关矩阵/整数快速幂/乘

参考来源： [整数快速乘法，整数快速幂，矩阵快速幂【参考博客】][Link 1] [参考题目 poj 3070][poj 3070] 先说明一下基本的数学常识： >

朱雀/ 2022年03月10日 03:44/ 0 赞/ 243 阅读