89. a^b
题目大意
给 \(a,b,p\) 求 \(a^b \mod p\)。
思路
可以直接快速幂。当模数 \(p\) 为 \(1\) 的时候特判一下。
代码
ll a, b, mod;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod, b >>= 1;
}
return res;
}
int main() {
a = read(), b = read(), mod = read();
if (mod == 1) printf("0\n");
else printf("%lld\n", qpow(a, b));
return 0;
}
AcWing 90. 64位整数乘法
题目大意
给 \(a,b,p\) 求 \(a \times b \mod p\)。
思路1
好像是想让我写龟速乘，但是我直接 __int128 莽过去了（）。
代码1
__int128 a, b, mod;
void prt(__int128 x) {
if (x > 9) prt(x / 10);
putchar(x % 10 + '0');
}
int main() {
a = read(), b = read(), mod = read();
__int128 ans = a * b % mod;
prt(ans);
return 0;
}
思路2
龟速乘，长得和快速幂很像。
代码2
ll a, b, mod;
ll mul(ll a, ll b) {
ll res = 0;
while (b) {
if (b & 1) res = (res + a) % mod;
a = (a << 1) % mod, b >>= 1;
}
return res;
}
int main() {
a = read(), b = read(), mod = read();
printf("%lld\n", mul(a, b));
return 0;
}