[练习记录] 《算法竞赛进阶指南》打卡活动

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;
}