【題解】Codeforces 1228C. Primes and Multiplication

【Problem】https://codeforces.com/problemset/problem/1228/C
【Solution:】Exponentiating by Squaring (快速冪)

  • pow_mod(a, b): standard implementaion of Binary Exponentiation
  • See the illustration below.
#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
const int MOD = 1e9+7;

ll pow_mod(ll a, ll b){
    //快速冪 (a^b) % MOD
    ll ret = 1;
    ll now = a;
    while (b) {
        // b = 5 = b'101
        // a^b = a^5 = a^4 * a^1
        if (b & 1) {
            // 需要這個冪次
            ret *= now;
            ret %= MOD;
        }
        now *= now; // a -> a^2 -> a^4 -> ...
        now %= MOD; // avoid overflow
        b >>= 1; // b 的二進位數字往右移一位元
    }
    return ret;
}

int main() {
    int x; // 2≤𝑥≤10^9
    ll n; // 1≤𝑛≤10^18
    ll ans;
    // Calculate 𝑓(𝑥,1)⋅𝑓(𝑥,2)⋅…⋅𝑓(𝑥,𝑛)mod(10^9+7).
    // 𝑓(30,70)=𝑔(70,2)⋅𝑔(70,3)⋅𝑔(70,5)=2^1⋅3^0⋅5^1=10
    while (cin >> x >> n){
        ans = 1;
        // search all 𝑝 in 𝑝𝑟𝑖𝑚𝑒(𝑥)
        int sq = sqrt(x);
        for (ll p=2; p<=sq; p++){
            if (x % p != 0) continue;
            while (x % p == 0) x /= p;
            
            ll cnt = 0;
            ll num = n;
            while (num){
                cnt += num / p;
                num /= p;
            }
            ans *= pow_mod(p, cnt);
            ans %= MOD;
        }
        if (x > 1){
            ll p = x;
            ll cnt = 0;
            ll num = n;
            while (num){
                cnt += num / p;
                num /= p;
            }
            ans *= pow_mod(p, cnt);
            ans %= MOD;
        }
        cout << ans << '\n';
    }
    return 0;
}
分享本文 Share with friends