题解：P10663 BZOJ4833 最小公倍佩尔数
Eric998
·
·
题解
首先知道 \gcd(f_x,f_y)=f_{\gcd(x,y)}。证明同 fib 的情况。
枚举 $\gcd$，设为 $d$。考虑每个 $d$ 对答案的贡献。首先里面有个 $\displaystyle\sum_{S\in{1,\dots,\frac nd},S\neq \empty}(-1)^{|S|+1}$。观察到 $\displaystyle\sum_{S\in{1,\dots,\frac nd}}(-1)^{|S|+1}=-(1-1)^{\frac nd}=0$，再把空集去掉得到 $\displaystyle\sum_{S\in{1,\dots,\frac nd},S\neq \empty}(-1)^{|S|+1}=1$。
对于 $\gcd$ 为 $d$ 的集合 $T$，设 $\displaystyle h_i=\sum(-1)^{|T-1|}$，有 $\displaystyle\sum_{d=1}^{\frac nd} h_{id}=1$。扫描 $i$ 的时候，$h*1$ 在后面会接上一个 $1$，因此 $h_d(d|i)$ 会加上 $\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();
}
```