蓝桥

约 179 个字 21 行代码 预计阅读时间 1 分钟

Solve Problems

要快速计算 a^b % p, 1≤ ai,bi,pi ≤2×10^9

1. 先考虑一个暴力解法， 即循环求出 a^b, 时间复杂度 O(b)
2. 再考虑优化, 设 b 的二进制表示为 b', 即 a^b = a^(b'0 * 2^0) + a^(b'1 * 2^0) + a^(b'2 * 2^0) + ... + a^(b'i * 2^i), 这样 a^b计算的实践复杂度就为 log2(b)

求余运算性质

1. 恒等律：a % p = a，当 a < p 时。这意味着任何小于模数 p 的数对 p 取模的结果就是它本身。
2. 加法和减法的模运算：
   • (a + b) % p = (a % p + b % p) % p
   • (a - b) % p = (a % p - b % p) % p
3. 乘法的模运算：
   • (a * b) % p = (a % p * b % p) % p
4. 指数的模运算：
   • (a^b) % p = ((a % p)^b) % p

代码

#include<bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    int n;
    cin >> n;
    while(n--){
        LL res = 1;
        LL a, b, p;
        cin >> a >> b >> p;
        while(b){
            if(b & 1)res = res * a % p;
            b = b >> 1;
            a = a * a % p;
        }
        cout << res << '\n';
    }

    return 0;
}

评论