【JZOJ5250】【GDOI2018模拟】质数(数论)

Description

Solution

要求2f(i)可以考虑狄利克雷卷积一下，或者讨论一下其中的性质。
对于所有不同的质因子，然后再2的次幂一下，很明显可以知道是选与不选的问题。
那么要求2f(i)就相当于求∑j|i[gcd(j,i/j)==1]
我们要求gcd为1的个数可以考虑容斥一下。
那么上式就转化成∑j|i∑d|gcd(j,i/j)μ[d]
我们先枚举d，设ik=j，因为d|i/j，所以d2|ik
那么式子变成∑d2|iμ[d]∑id2k=1[d2k|i]
然后后面的式子就变成∑d2|iμ[d]g(id2)
g(i)表示i的约数个数
然后再把d提出来式子就变成
∑n√d=1μ[d]∑nd2k=1g(d2kd2)
式子等于∑n√d=1μ[d]∑nd2k=1nd2k
然后直接暴力就好了

Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=1e6+7,mo=998244353;
ll i,j,k,l,t,m,ans,q,n,r;
int er[21],p[maxn],mu[maxn],s[maxn];
bool bz[maxn];
int main(){
//  freopen("fan.in","r",stdin);
    fo(i,2,maxn-7){
        if(!bz[i])p[++p[0]]=i,mu[i]=-1;
        fo(j,1,p[0]){
            t=p[j]*i;if(t>maxn-7)break;
            bz[t]=1;if(i%p[j]==0){break;}
            mu[t]=-mu[i];
        }
    }
    mu[1]=1;
    scanf("%lld",&n);
    fo(i,1,sqrt(n)){
        q=0;t=n/(i*i);
        l=1;
        while(l<=t){
            r=t/(t/l);
            q=(q+(r-l+1)*(t/l))%mo;
            l=r+1;
        }
        ans=(ans+mu[i]*q)%mo;
    }
    ans=(ans+mo)%mo;
    printf("%lld\n",ans);
}