JZOJ 5250 质数

首先转换一下，考虑 2f(i) 的组合意义。
相当于把 i 的不同质因子分别分到两个数里面。
于是 2f(i)=∑d|i[gcd(d,id)=1]。

于是就简单了。 n∑i=1∑d|i[gcd(d,id)=1]=n∑d=1∑id≤n[gcd(d,i)=1]=n∑d=1∑id≤n∑k|gcd(d,i)μ(k)=∑k2≤nμ(k)∑ik2≤n⌊nik2⌋=⌊√n⌋∑k=1μ(k)⌊nk2⌋∑i=1⌊nik2⌋

枚举 k 然后数论分块算后面的式子就好了，大概是 O(√nlogn) 的样子？
注意取模呀……n 是会爆模数的……

代码：

#include <cstdio>
#include <cmath>
using namespace std;
const int MX = 1e6;
const long long mod = 998244353;
long long n;
int vis[MX + 5],prime[MX + 5],cnt;
long long mu[MX + 5];
long long ans;
int main()
{
    mu[1] = 1;
    for(register int i = 2;i <= MX;++i)
    {
        if(!vis[i])
            mu[prime[++cnt] = i] = mod - 1;
        for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
            else
                mu[i * prime[j]] = mod - mu[i];
        }
    }
    scanf("%lld",&n);
    for(register int i = 1;(long long)i * i <= n;++i)
    {
        long long s = 0;
        for(register long long l = 1,r,lim = n / i / i;l <= lim;l = r + 1)
        {
            r = lim / (lim / l);
            s = (s + (lim / l) % mod * (r - l + 1) % mod) % mod;
        }
        ans = (ans + s * mu[i] % mod) % mod;
    }        
    printf("%lld\n",ans);
}