#C241111D. 集合操作
标签（Label）
- 期望
- 数学
网址（Website）
题目（Problem）
题解（Solution）
$\qquad$只打了 $\text{60pts}$ ，和今天的 $E$ 题一样，类似的想法，输出 $\sum_{i=1}^{i\le n}\frac{1}{dep_i}$ 。
出题者题解
算法分析
【对于60分的做法】
请参考CF280C：
考虑对问题做如下转化：随机一个排列 $P$，第 $i$ 次操作删除 $P_i$ 的倍数，但如果 $P_i$ 已经被删除则不计入次数。
由期望线性性，答案是每个 $P_i$ 被记入次数的概率之和。也就是 $P_i$ 与其因子们，$P_i$ 是在排列里第一个出现的概率，也就是 $\frac{1}{d_{P_i}}$，其中 $d_u$ 是 $u$ 的因子个数。
令 $f(x) = \frac{1}{d_x}$，容易发现 $f(x)$ 是积性函数，可以线性筛，获得部分分。
【对于100分的做法】
可以使用 min25/洲阁筛 实现。
总之选取你喜欢的筛子，可以得到 $O(n^{1-\epsilon})$ 或 $O(\frac{n^{\frac{3}{4}} }{\log n})$ 之类的复杂度。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i++)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;
double Tim;
int n,ans,mod,dep[N];
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void mul(int &x,int y){x=x*y%mod;}
inline int ksm(int x,int k){
int res=1;while(k){
if(k&1) mul(res,x);
mul(x,x),k>>=1;
}return res;
}
void Solve(){
n=rd(),mod=rd();
For(i,1,n) for(int j=i;j<=n;j+=i) dep[j]++;
For(i,1,n) add(ans, ksm(dep[i],mod-2));
printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
int Tt=1;Tim=clock();
while(Tt--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
