给出a,b,c。令p=1000000007, z=b^c, y=a^z, x=y mod p。请求出x。
三个整数分别是a,b,c
请输出x
abc都不超过10^9
不能使用a^(b^c%mod)%mod
考虑费马小定理
当a和p互质时, a ^ (p - 1) % p = 1
最后的结论是a^(b^c) % mod = a^(b^c%(mod - 1)) % mod
先是一个结论:a = b * (a / b) + a % b
div = (b ^ c) / (mod - 1)
rem = (b ^ c) % (mod - 1)
则a^(b^c) % mod = a ^ ((mod - 1) * div + rem) % mod
由于a小于1e9,mod=1e9+7, mod是质数,a和mod互质,满足费马小定理
所以,a^(b^c) % mod = a ^ rem % mod
#include <iostream> using namespace std; const int p = 1000000007; typedef long long LL; int qmi(int a, int k, int mod) { int res = 1; while(k) { if(k & 1) { res = (LL)res * a % mod; } a = (LL)a * a % mod; k >>= 1; } return res; } int main() { int a, b, c; cin >> a >> b >> c; int z = qmi(b, c, p - 1); int y = qmi(a, z, p); cout << y; return 0; }