【JZOJ5250】【GDOI2018模拟8.11】质数

Description

Data Constraint

Solution

我们发现 2f(n) 就等于 ∑i|n[gcd(i,n/i)==1]
所以题目就是求：

∑i=1n∑j|i[gcd(j,i/j)==1]

=∑j=1n∑i=1⌊n/j⌋[gcd(i,j)==1]

=∑j=1n∑i=1⌊n/j⌋∑d|gcd(i,j)μ(d)

=∑d=1n√μ(d)∑k=1⌊n/d⌋⌊⌊n/d2⌋k⌋

枚举d，然后分块计算后面即可。

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll maxn=1e6+5,mo=998244353; 
ll bz[maxn],u[maxn],n,i,t,j,k,l,x,y,z,d[maxn],ans,p[maxn];
ll dg(ll n){
    ll t,i=1,x=0;
    while (i<=n){
        t=n/(n/i);
        x=x+n/i*(t-i+1)%mo;i=t+1;
    }
    return x%mo;
}
int main(){
//  freopen("data.in","r",stdin);
    scanf("%lld",&n);u[1]=1;t=sqrt(n);
    for (i=2;i<=t;i++){
        if (!bz[i]) bz[i]=1,d[++d[0]]=i,u[i]=-1;
        for (j=1;j<=d[0];j++){
            if (i*d[j]>t) break;
            u[i*d[j]]=-u[i];bz[i*d[j]]=1;
            if (i%d[j]==0){
                u[i*d[j]]=0;
                break;
            }
        }
    }
    for (i=1;i<=t;i++)
        ans=ans+u[i]*dg(n/(i*i));
    ans=(ans%mo+mo)%mo;
    printf("%lld\n",ans);
}