#线性筛求约数个数+逆元# [nssl 1520] 小清新期望题

Title

注意范围

---

Solution

1. 性质当然很重要
2. 注意用线性筛求约数个数的方法

图片转载于：https://www.cnblogs.com/TheRoadToTheGold/p/8228969.html

3. 注意此题卡时间 ，可以优化一下
   .

---

Code（90）

#include<cstdio>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std; 
const int N=20000011,mod=998244353; 
int m,prime[N],q,f[N],ans,inv[N],w[N]; 
void linear(int n){
	inv[1]=1; 
	rep(i,2,n){
		if (!w[i]) prime[++m]=i,w[i]=inv[i]=2; 
		rep(j,1,m){
			if (prime[j]>n/i) break;
			if(i%prime[j]==0) {
				w[i*prime[j]]=w[i]+1,inv[i*prime[j]]=inv[i]/w[i]*w[i*prime[j]]; 
				break;
			}
			else w[i*prime[j]]=2,inv[i*prime[j]]=inv[i]<<1; 
		}
	}
}
int main(){
	linear(N-11); 
	scanf("%d",&q); 
	f[1]=1; 
	rep(i,2,N/10) f[i]=1ll*(mod-mod/i)*f[mod%i]%mod; 
	rep(i,1,q) ans=(ans+f[inv[i]])%mod;  
	printf("%d",ans); 
	return 0; 
}