Solution

我的方法有一点点笨拙，但比较好想，也比较好理解吧。

诸君且看：

a=\prod_{i=1}^{n}{p_i}^{k_i}

则

\begin{aligned} \varphi(a^b)&=\varphi(\prod_{i=1}^{n}{p_i}^{k_i b}) \\ &=\prod_{i=1}^{n}{\varphi({p_i}^{k_i b})} \\ &=\prod_{i=1}^{n}{p_i^{k_i b-1}(p_i-1)} \end{aligned}

考虑一下时间复杂度。使用快速幂计算每个

p_i^{k_i b-1}

需要

\log(k_i b-1)

，最大

64

左右；

n

最大是

\sqrt{a}

；那么总的时间复杂度就是

O(64\sqrt{a})

，能够通过本题。

代码和思路部分完全一致，也放在这里了。

CPP

#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int MOD = 998244353;
int a, b, ans = 1;
vector<pair<int, int> > p;
void Prime(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			p.push_back(make_pair(i, 0));
			while (n % i == 0) n /= i, p.back().second++;
            p.back().second *= b;
		}
	}
	if (n > 1) p.push_back(make_pair(n, b));
}
int Pow(int x, int n) {
	int res = 1;
	while (n) {
		if (n & 1) (res *= x) %= MOD;
		(x *= x) %= MOD;
		n >>= 1;
	}
	return res;
}
signed main() {
	cin >> a >> b;
	Prime(a);
	for (int i = 0; i < p.size(); i++) {
		int t = p[i].first, cnt = p[i].second;
		(ans *= (t - 1) * Pow(t, cnt - 1) % MOD) %= MOD;
	}
	cout << ans << '\n';
	return 0;
}

题解：P13880 [蓝桥杯 2023 省 Java A] 互质数的个数

文章操作

Solution

相关推荐

评论

题解：P13880 [蓝桥杯 2023 省 Java A] 互质数的个数