专栏文章

题解：P10663 BZOJ4833 最小公倍佩尔数

EEric998
P10663题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minl2s2o
此快照首次捕获于
2025/12/02 04:10
3 个月前
此快照最后确认于
2025/12/02 04:10
3 个月前
查看原文
首先知道 gcd⁡(fx,fy)=fgcd⁡(x,y)\gcd(f_x,f_y)=f_{\gcd(x,y)}。证明同 fib 的情况。
gcd⁡\gcd 好求，问 lcm⁡\operatorname{lcm}，考虑 min⁡−max⁡\min-\max 容斥，lcm⁡(f1,…,fn)=∏S∈1,…,ngcd⁡pp∈S(fp)−1∣S∣+1=∏S∈1,…,nfgcd⁡pp∈S(p)−1∣S∣+1\displaystyle\operatorname{lcm}(f_1,\dots,f_n)=\prod_{S\in{1,\dots ,n}}\gcd_p^{p\in S}(f_p)^{-1^{|S|+1}}=\prod_{S\in{1,\dots ,n}}f_{\gcd_p^{p\in S}(p)}^{-1^{|S|+1}}.
枚举 gcd⁡\gcd，设为 dd。考虑每个 dd 对答案的贡献。首先里面有个 ∑S∈1,…,nd,S≠∅(−1)∣S∣+1\displaystyle\sum_{S\in{1,\dots,\frac nd},S\neq \empty}(-1)^{|S|+1}。观察到 ∑S∈1,…,nd(−1)∣S∣+1=−(1−1)nd=0\displaystyle\sum_{S\in{1,\dots,\frac nd}}(-1)^{|S|+1}=-(1-1)^{\frac nd}=0，再把空集去掉得到 ∑S∈1,…,nd,S≠∅(−1)∣S∣+1=1\displaystyle\sum_{S\in{1,\dots,\frac nd},S\neq \empty}(-1)^{|S|+1}=1。
对于 gcd⁡\gcd 为 dd 的集合 TT，设 hi=∑(−1)∣T−1∣\displaystyle h_i=\sum(-1)^{|T-1|}，有 ∑d=1ndhid=1\displaystyle\sum_{d=1}^{\frac nd} h_{id}=1。扫描 ii 的时候，h∗1h*1 在后面会接上一个 11，因此 hd(d∣i)h_d(d|i) 会加上 μ(id)\mu(\frac id)。直接求即可。
CPP
#include <bits/stdc++.h>
using namespace std;
#define N 5000005
#define int long long
int e[N], f[N], d[N], mu[N], I[N], prm[N], n, p, T, cur, ans;

int pw(int a, int t) {
	if (!t)
		return 1;
	int x = pw(a, t >> 1);
	x = x * x % p;
	if (t & 1)
		x = x * a % p;
	return x;
}

void solve() {
	e[0] = 1, cin >> n >> p, cur = 1, ans = 0;
	for (int i = 1; i <= n; i++)
		f[i] = (e[i - 1] + f[i - 1]) % p, e[i] = (e[i - 1] + f[i - 1] * 2) % p, I[i] = pw(f[i], p - 2), d[i] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j += i)
			d[j] = d[j] * (mu[j / i] ? ((~mu[j / i]) ? f[i] : I[i]) : 1) % p;
	for (int i = 1; i <= n; i++)
		cur = cur * d[i] % p, ans = (ans + i * cur) % p;
	cout << ans << '\n';
}

main() {
	for (int i = 1; i < N; i++)
		mu[i] = 1;
	for (int i = 2; i < N; i++)
		if (!prm[i]) {
			for (int j = i; j < N; j += i)
				prm[j] = 1, mu[j] = -mu[j];
			for (int j = i * i; j < N; j += i * i)
				mu[j] = 0;
		}
	cin >> T;
	while (T--)
		solve();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...