题解：P7360 「JZOI-1」红包

前言：

好题啊，可惜各位大佬的莫反，容斥，一堆的式子我都看不懂啊，只看懂了 Corzica 大佬的做法，这里主要是对其做法的补充解释。

思路：

首先考虑对于每个质数

p

，它对答案的贡献：若

\operatorname{lcm}

中含有

p^q

，总共有

n^k

种方案，其中

\operatorname{lcm}

不含

p^q

的方案数是

n^k-(\frac{n}{p^q})^k

，相减就是含

\operatorname{lcm}

的方案。对答案的贡献是

p^{n^k-(\frac{n}{p^q})^k}

，为啥底数不是

p^q

呢，因为我们已经统计过了

\operatorname{lcm}

含有

p^{q-1},p^{q-2}...p

了，

p^q

只多了

p

的贡献，所以底数是

p

。

又因为读入的

k

很大，根据扩展欧拉定理和费马小定理，对于指数上的

n^k

，

k

模

φ(mod-1)

即可，指数的答案再模

mod-1

。这样单次时间是

O(n\log{n})

的，对于

\frac{n}{p^q}

，发现可以整除分块，单次时间复杂度降至

O(\sqrt{n}\log{n})

，可以通过。还有别的问题就看代码吧，实现也是比较简单的。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int mod = 998244353;
const int phi = 402653184;//998244352 的phi值
int n, m, pr[N], cnt, f[N], T;
bool vis[N];
//快速幂
inline int quickpow(int x, int y, int mod) {
	if (y == 1)return x;
	if (y == 0)return 1;
	int g = quickpow(x, y / 2, mod);
	if (y & 1)return g * g % mod * x % mod;
	return g * g % mod;
}
signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//f[i]记录i这个数是不是一个质数的 n 次方，是的话，是哪个质数，可以线性筛预处理
	n = 1e6;
	for (int i = 2; i <= n; i ++) {
		if (!vis[i]) {
			pr[++ cnt] = i;
			f[i] = i;
		}
		for (int j = 1; j <= cnt && i * pr[j] <= n; j ++) {
			vis[pr[j] * i] = 1;
			if (i % pr[j] == 0) {
				f[i * pr[j]] = f[i];
				break;
			}
		}
	}
	f[0] = 1;
	for (int i = 1; i <= n; i ++) {
		if (!f[i])f[i] = 1;
		f[i] = f[i - 1] * f[i] % mod;
	}
	//预处理前缀积
	cin >> T;
	while (T --) {
		cin >> n;
		string s;
		cin >> s;
		m = 0;
		for (int i = 0; i < s.size(); i ++) {
			m = m * 10 + s[i] - '0';
			if (m >= phi) m = m % phi + phi;
		}//读入时将k 模 φ(mod - 1),因为 k 在最后的式子上在指数的指数上
		int all = quickpow(n, m, mod - 1), ans = 1;
		//总是用 n ^ k 去减，可以直接算好
		for (int l = 1; l <= n; l ++) {
			int r = n / (n / l);//整除分块
			if (f[r] != f[l - 1]) {
				//f[r] / f[l - 1] 求 l ~ r 的积
				ans *= quickpow(f[r] * quickpow(f[l - 1], mod - 2, mod) % mod, (all - quickpow(n - n / l, m, mod - 1)/*减去 lcm 中没有 p ^ q 的方案*/ + mod - 1) % (mod - 1), mod);
				ans %= mod;
			}
			l = r;
		}
		cout << ans << '\n';
	}
	return 0;
}

题解：P7360 「JZOI-1」红包

文章操作

前言：

思路：

相关推荐

评论

题解：P7360 「JZOI-1」红包