题目链接:洛谷
这个公式可真是个好东西。(哪位大佬知道它叫什么名字的?)
如果$X$恒$geq 0$,那么
$$E[X]=int_0^{+infty}P(X>t)dt$$
呸,我什么都没写。
如果$Xin N$,那么
$$E[X]=sum_{i=0}^{+infty}P(X>i)$$
根据上面的公式,我们首先看看如何计算$P(X>i)$
这个表示前$i$个数的$gcd$不为1,我们反面考虑,$gcd$为1的概率可以通过莫比乌斯反演求出,所以
$$P(X>i)=1-sum_{d=1}^mmu(d)(frac{lfloorfrac{m}{d} floor}{m})^i$$
$$=-sum_{d=2}^mmu(d)(frac{lfloorfrac{m}{d} floor}{m})^i$$
带入上面的公式。
$$E[X]=sum_{i=1}^{+infty}P(x>i)+1$$
$$=1-sum_{i=1}^{+infty}sum_{d=2}^mmu(d)(frac{lfloorfrac{m}{d} floor}{m})^i$$
$$=1-sum_{d=2}^{m}mu(d)sum_{i=1}^{+infty}(frac{lfloorfrac{m}{d} floor}{m})^i$$
$$=1-sum_{d=2}^mmu(d)frac{lfloorfrac{m}{d} floor}{m-lfloorfrac{m}{d} floor}$$
预处理$mu$和$inv$之后,时间复杂度$O(m)$
1 #include<cstdio> 2 #define Rint register int 3 using namespace std; 4 typedef long long LL; 5 const int N = 100003, mod = 1e9 + 7; 6 inline int add(int a, int b){int res = a + b; if(res >= mod) res -= mod; return res;} 7 inline int dec(int a, int b){int res = a - b; if(res < 0) res += mod; return res;} 8 int n, mu[N], pri[N], tot, inv[N], ans, tmp; 9 bool notp[N]; 10 int main(){ 11 scanf("%d", &n); 12 inv[1] = 1; 13 for(Rint i = 2;i <= n;i ++) inv[i] = (LL) (mod - mod / i) * inv[mod % i] % mod; 14 notp[0] = notp[1] = true; 15 mu[1] = 1; 16 for(Rint i = 2;i <= n;i ++){ 17 if(!notp[i]){mu[i] = mod - 1; pri[++ tot] = i;} 18 for(Rint j = 1;j <= tot && i * pri[j] <= n;j ++){ 19 notp[i * pri[j]] = true; 20 if(i % pri[j]) mu[i * pri[j]] = mod - mu[i]; 21 else break; 22 } 23 } 24 for(Rint i = 2;i <= n;i ++){ 25 tmp = n / i; 26 ans = add(ans, (LL) mu[i] * tmp % mod * inv[n - tmp] % mod); 27 } 28 printf("%d", dec(1, ans)); 29 }