H-大數乘法

題目描述

Problem Description

給定a，b，c，要求按照以下程式計算ans：

ans=1

for(i=1;i<=b;i++){

ans=ans*a;

}

ans%=c

輸出ans

小明發現這看起來就是大數乘法和大數取模的裸題，但是他忘了怎麼寫了，請你幫幫他！

Input

多組輸入，每組資料一行，每行給出3個正整數a，b，c （1<=a,b,c<=1e18）

Output

每組資料輸出一行，為答案

Sample Input

2 10 10000000
5 100 1
0 2 37      

Sample Output

1024
0
0      

題目分析

題目給的代碼一定不是能AC的代碼讀一下題目中的代碼，不難發現題目的要求：給定，求，資料範圍非常大，不适合用普通求幂取模方法得到。

求幂的優化：快速幂+大數相乘取模 = 快速大數幂

快速幂闆子：

int qpow(int a, int b) {
    int ans = 1, base = a;
    while (b != 0) {
        if (b & 1) ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}      

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

ll qpow_mod(ll a, ll n, ll mod) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = qmul(ret, a, mod);
        a = qmul(a, a, mod);
        n >>= 1;
    }
    return ret;
}      

AC Code

#include <iostream>
#define
#define
using namespace std;
ll a, b ,c;

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

ll qpow_mod(ll a, ll n, ll mod) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = qmul(ret, a, mod);
        a = qmul(a, a, mod);
        n >>= 1;
    }
    return ret;
}

int main(){
    IOF;
    while (cin >> a >> b >> c){
        cout << qpow_mod(a, b, c) << endl;
    }
    return 0;
}