题意
每次从 [ 1 , n ] [1,n] [1,n] 中选择一个数加到一个序列末尾,当 gcd ( a 1 , ⋯ , a n ) = 1 \gcd(a_1,\cdots,a_n)=1 gcd(a1,⋯,an)=1 时停止,求期望长度,对 p p p 取模
1 ≤ n ≤ 1 0 11 , n < p ≤ 1 0 12 1\le n \le 10^{11},n< p \le 10 ^{12} 1≤n≤1011,n<p≤1012
分析:
设 E ( l e n ) E(len) E(len) 为期望长度,那么根据期望定义
E ( l e n ) = ∑ i = 1 ∞ P ( l e n = i ) ⋅ i E(len)=\sum_{i=1}^{\infty}P(len=i) \cdot i E(len)=i=1∑∞P(len=i)⋅i
把 i i i 改为 ∑ j = 1 i 1 \sum\limits_{j=1} ^{i}1 j=1∑i1
E ( l e n ) = ∑ i = 1 ∞ P ( l e n = i ) ∑ j = 1 i 1 E(len)=\sum_{i=1}^{\infty}P(len=i) \sum_{j=1}^{i}1 E(len)=i=1∑∞P(len=i)j=1∑i1
交换求和次序
∑ j = 1 ∞ 1 ∑ i = j ∞ P ( l e n = i ) \sum_{j=1}^{\infty}1\sum_{i=j}^{\infty}P(len=i) j=1∑∞1i=j∑∞P(len=i)
化简一下
∑ i = 1 ∞ P ( l e n ≥ i ) = 1 + ∑ i = 1 ∞ P ( l e n > i ) \sum_{i=1}^{\infty}P(len \ge i)=1+\sum_{i=1}^{\infty}P(len > i) i=1∑∞P(len≥i)=1+i=1∑∞P(len>i)
考虑 P ( l e n > i ) P(len > i) P(len>i),进行容斥 1 − P ( l e n ≤ i ) 1-P(len \le i) 1−P(len≤i) 就等价于
1 − P ( gcd ( a 1 , ⋯ , a i ) = 1 ) 1-P(\gcd(a_1,\cdots,a_i)=1) 1−P(gcd(a1,⋯,ai)=1)
枚举 a i a_i ai 在 [ 1 , n ] [1,n] [1,n] 中的取值
1 − ∑ a 1 = 1 n ⋯ ∑ a i = 1 n [ gcd ( a 1 , ⋯ , a i ) = 1 ] n i 1-\sum_{a_1=1}^{n}\cdots\sum_{a_i=1}^{n}\frac{[\gcd(a_1,\cdots,a_i)=1]}{n^{i}} 1−a1=1∑n⋯ai=1∑nni[gcd(a1,⋯,ai)=1]
莫比乌斯反演
1 − ∑ a 1 = 1 n ⋯ ∑ a i = 1 n ∑ d ∣ gcd ( a 1 , ⋯ , a i ) μ ( d ) n i 1-\sum_{a_1=1}^{n}\cdots\sum_{a_i=1}^{n}\frac{\sum\limits_{d \mid\gcd(a_1,\cdots,a_i) }\mu(d)}{n^{i}} 1−a1=1∑n⋯ai=1∑nnid∣gcd(a1,⋯,ai)∑μ(d)
交换求和次序
1 − ∑ d = 1 n μ ( d ) ⌊ n d ⌋ i n i 1-\frac{\sum\limits_{d=1}^{n}\mu(d)\lfloor \dfrac{n}{d} \rfloor^i}{n^i} 1−nid=1∑nμ(d)⌊dn⌋i
把 1 1 1 拿到分子,和第一项抵消了
− ∑ d = 2 n μ ( d ) ⌊ n d ⌋ i n i -\frac{\sum\limits_{d=2}^{n}\mu(d)\lfloor \dfrac{n}{d} \rfloor^i}{n^{i}} −nid=2∑nμ(d)⌊dn⌋i
代入到 1 + ∑ i = 1 ∞ P ( l e n > i ) 1+\sum\limits_{i=1}^{\infty}P(len > i) 1+i=1∑∞P(len>i) 得
1 − ∑ i = 1 ∞ ∑ d = 2 n μ ( d ) ⌊ n d ⌋ i n i 1-\sum_{i=1}^{\infty}\frac{\sum\limits_{d=2}^{n}\mu(d)\lfloor \dfrac{n}{d} \rfloor^i}{n^{i}} 1−i=1∑∞nid=2∑nμ(d)⌊dn⌋i
交换求和次序
1 − ∑ d = 2 n μ ( d ) ∑ i = 1 ∞ ( ⌊ n d ⌋ n ) i 1-\sum_{d=2}^{n}\mu(d)\sum_{i=1}^{\infty}(\frac{\lfloor \dfrac{n}{d} \rfloor}{n})^i 1−d=2∑nμ(d)i=1∑∞(n⌊dn⌋)i
∑ i = 1 ∞ ( ⌊ n d ⌋ n ) i \sum\limits_{i=1}^{\infty}(\dfrac{\lfloor \dfrac{n}{d} \rfloor}{n})^i i=1∑∞(n⌊dn⌋)i 这是个等比级数,极限为 首 项 1 − 公 比 \dfrac{首项}{1-公比} 1−公比首项
1 − ∑ d = 2 n μ ( d ) ⌊ n d ⌋ n − ⌊ n d ⌋ 1-\sum_{d=2}^{n}\mu(d)\frac{\lfloor \dfrac{n}{d} \rfloor}{n-\lfloor \dfrac{n}{d} \rfloor} 1−d=2∑nμ(d)n−⌊dn⌋⌊dn⌋
就可以用杜教筛了
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2.2e7 + 5;
int n, mod, mobius[N], primes[N], cnt, sum[N], res = 1;
bool st[N];
unordered_map<int, int> mp;
int qmul(int a, int b) {
return (__int128)a * b % mod;
}
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = qmul(res, a) % mod;
a = qmul(a, a) % mod;
b >>= 1;
}
return res;
}
void get_mobius(int n) {
mobius[1] = 1;
for (int i = 2; i <= n; i ++) {
if (!st[i]) {
primes[cnt ++] = i;
mobius[i] = -1;
}
for (int j = 0; primes[j] * i <= n; j ++) {
int t = primes[j] * i;
st[t] = 1;
if (i % primes[j] == 0) {
mobius[t] = 0;
break;
}
mobius[t] = -mobius[i];
}
}
for (int i = 1; i <= n; i ++) sum[i] = (sum[i - 1] + mobius[i] + mod) % mod;
}
int Sum(int n) {
if (n < N) return sum[n];
if (mp[n]) return mp[n];
int res = 1;
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
res = (res - qmul(Sum(n / l), r - l + 1) + mod) % mod;
}
return mp[n] = res;
}
signed main() {
cin >> n >> mod;
get_mobius(N - 1);
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
res = (res - qmul(Sum(r) - Sum(l - 1), qmul((n / l) % mod, qmi(n - n / l, mod - 2))) % mod + mod) % mod;
}
cout << res << endl;
}