快速乘 + 快速幂 + 取模

忘是亡心i 2022-06-08 09:38 221阅读 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 条评论，221人围观）

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

相关阅读

相关【数论】快速幂、矩阵快速幂取模专题训练

前言 HDU-1061 Rightmost Digit（快速幂取模） HDU-2817 A sequence of numbers（快速幂取模）

你的名字/ 2023年07月01日 07:30/ 0 赞/ 74 阅读

相关 ACM.快速幂取模

给你一个数a，让你求其b次连乘后的结果当b很小时，一般的循环算法可以解决这个问题(O(B))，但是当b较大时呢要知道1e18以上，就会long long int 也

落日映苍穹つ/ 2023年06月29日 07:27/ 0 赞/ 59 阅读

相关数论-快速幂、矩阵快速幂、慢速乘

文章目录快速幂矩阵快速幂慢速乘例题 HDU-2817 HDU-3117 XUJC-1395 快

朱雀/ 2023年03月05日 09:41/ 0 赞/ 67 阅读

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

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

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

相关快速幂取模及其应用

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

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

相关快速幂取模算法模板

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

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

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

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

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

相关 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 赞/ 236 阅读

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

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

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

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

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

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