题解 P4900 【食堂】

· · 题解

不得不说，这题目是一道对于noip选手的数论好题，涉及的知识点比较多，算法也都不是很难，但是很具有思考性。
首先，我们对于每一个i，来枚举（打表）出它所对应的值。 然后，我们发现，对于第i-1行，如果它要变成第i行，我们就增加从1/2~1/i-1（也就是逆元之和，用前缀和来维护）,然后再减去它的约数,就可以得到这一行的和了qwq（不包括1和它自己，想一想为什么）
然后递推即可(Ｏ(≧口≦)Ｏ,我一开始以为有啥数学方法诶)
话说CYJian的题目怎么这么多离线算法，而且这次比赛这么多筛法
顺带附上知识点所需的模板：
同余方程
乘法逆元
筛素数（稍微改一改就可以筛约数）
代码（本人用的是埃氏筛，不知道为啥比标程的欧拉筛还快（玄学），不过从1-n的每个数的约数之和接近nlnn吧（也就是说欧拉筛应该是被卡了））

#include<vector>
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1000000,p=998244353;
int inv[N+1],f[N+1],sum[N+1],prime[N+1];
void pre(){
    inv[1]=1;
    for(int i=2;i<=N;i++)   
        inv[i]=(((long long)-inv[p%i]*(p/i))%p+p)%p;
    for(int i=2;i<=N;i++)
        sum[i]=((long long)sum[i-1]+inv[i])%p;
    for(int i=2;i<=N;i++)
        for(int j=i+i;j<=N;j+=i)
            prime[j]++;//注意，这里的prime指的是j的约数（除了1和它自己）的和，打习惯prime了qwq，大家将就一下
    for(int i=3;i<=N;i++){
        long long cnt=0;
        cnt=(f[i-1]-f[i-2]+p)%p+sum[i-1];
        cnt=(cnt+p-prime[i]+f[i-1])%p;  f[i]=cnt;//f[i]用前缀和的形式表示（后面要用）
    }
    return ;
}
int main(){
    int t; pre();
    cin>>t;
    while(t--){
        int a,b;
        scanf("%d%d",&a,&b);
        int ans=(((long long)f[b]-f[a-1])%p+p)%p;
        printf("%d\n",ans);
    }
    return 0;
}