[EOJ]#3349

URL:qwq

　　一道挺有意思的题。

　　在做这道题前，你需要知道：

　　　　\(*\)　$ \sum _{i=1}^{n} (\phi (i)* \lfloor \frac n i \rfloor)= \frac {n*(n+1)} 2$

　　　　\(*\)　$ \phi (i)= n*(\prod \frac 1 {p_i})$

　　然后就可以愉快的切题了（不是

　　我们的主要思路就是 \(\sum _{i=1}^{n} - \sum_{i=1}^{k} - \sum_{i=n-k+1}^{n}\) ，用全部的和减头减尾。其中第一项可以用上面的公式 \(1\) \(O(1)\) 求得，第二项由于欧拉函数有线性递推式（见代码的 \("euler"\) 函数），也可以暴力预处理。所以需要解决的就只剩下第三项了。

　　对于第三项的线性推肯定是行不通的，欧拉函数的线性递推式必须是已知前 \(n-1\) 项才必能求出第 \(n\) 项。时间和空间上都会爆掉。

　　直接使用欧拉函数筛法也不行，最坏情况 \(O(k\) \(\sqrt n)\)，会 \(T\) 的很悲惨。

　　也不能用杜教筛，因为我不会。

　　换种思路，现在我们知道了公式 \(2\) 。那么我们如果能在较短时间内 \(O(k\) \(log\) \(n)\) 求出每个 \(x \in [n-k+1,n]\) 的所有质因数，就可以完成程序。

　　方法当然是有的，就是线性筛素数的变种。枚举每个质数 \(p_i \in [1,\sqrt n]\) ，求出它在 \([n-k+1,n]\) 中的最小倍数，然后以 \(p_i\) 为步长，就可以把区间内所有 \(p_i\) 的倍数打上 \(tag\)，可以直接求出整个区间的答案 。

　　至于时间复杂度，应该是 \(\sum _{i=1}^{tot} \frac {n}{p_i}\)，是接近 $ O(k$ \(log\) \(n)\) 的。也就是说是可以 \(A\) 了此题的。

　　我大概是个傻子，考场上就是不预处理。

　　\(Tip:\) 可能会出现一些奇奇怪怪的事情，注意细节。

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n,k,tot,x,sum,ANS,F;
bool b[1000010];
int res[1000100],f[1000100][41],p[1000010];
inline void getp(ll n){
    for(ll i=2;i<=sqrt(n);i++){
        if(b[i])continue;
        p[++tot]=i;
        for(int j=2*i;j<=sqrt(n);j+=i)b[j]=1;
    }
} 
inline void euler()
{
    res[1]=1;
    for(int i=2;i<k;i++)
    {
        if(!res[i])
        {
            for(int j=i;j<k;j+=i)
            {
                if(!res[j])res[j]=j;
                res[j]=res[j]/i*(i-1);
            }
        }
    }
}
int main()
{
//    freopen("mogic.in","r",stdin);
//    freopen("mogic.out","w",stdout);
    cin>>n>>k;getp(n);euler();
    x=(n%mod)*((n+1)%mod)/2;
    for(ll i=1;i<k;i++)sum=(sum+res[i]*(n/i)%mod)%mod;
    for(ll i=1;i<=tot;i++){
        ll sq=ceil((double)(n-k+1)/(double)p[i])*p[i];
        for(ll j=sq;j<=n;j+=p[i])
        f[j-n+k][++f[j-n+k][0]]=i;
    }
    for(ll i=1;i<=k;i++){
        F=n-k+i;
        ll pr=n-k+i;
        for(int j=1;j<=f[i][0];j++){
            F=F/p[f[i][j]]*(p[f[i][j]]-1);
            while(!(pr%p[f[i][j]]))pr/=p[f[i][j]];
        }
        if(F==n-k+i)F--;
        else if(pr!=1)F=F/pr*(pr-1);
        sum=(sum+F*(n/(n-k+i)))%mod;
    }
    ANS=(x-sum+mod)%mod;cout<<ANS;
    return 0;
}

[EOJ]#3349

原文：https://www.cnblogs.com/alexiswithlucifer/p/11366197.html