(a ^ n mod p)
(a, p, n leq 10^9)
最普通的二进制拆分
#define LL long long
LL qpow(LL a, LL n, LL p)
{
LL ans = 1;
for (; n; n >>= 1, a = a * a % p)
if (n & 1)
ans = ans * a % p;
return ans % p;
}
(a, p, n leq 10^{14})
底数变大了,直接做(a * a)会爆longlong,需要用类似快速幂的方法做乘法
#define LL long long
LL mul(LL a, LL n, LL p)
{
LL ans = 0;
for (; n; n >>= 1, a = (a << 1) % p)
if (n & 1)
ans = (ans + a) % p;
return ans % p;
}
LL qpow(LL a, LL n, LL p)
{
LL ans = 1;
for (; n; n >>= 1, a = mul(a, a, p))
if (n & 1)
ans = mul(ans, a, p) % p;
return ans % p;
}
(a, p leq 10^{14}, n leq 10 ^ {100}) ((a perp p))
初看数据范围,出题人在搞事情。其实只是用了一个欧拉定理的结论:
[a^n equiv a^{n mod varphi(p)} pmod p (a perp p)
]
(O(sqrt{p}))算(varphi(p)),n先读字符串然后按快读的方式处理即可。
(a, p leq 10^{14}, n leq 10 ^ {100})
(a, p)互质的条件去掉了怎么办?当(n leq varphi(p))时可以直接算,否则用到以下结论:
[a^n equiv a^{n mod varphi(p) + varphi(p)} pmod p
]