Sum of the Line (容斥/莫比乌斯反演)

Sum of the Line

题意

给你一个n，分析之后发现求的是所有gcd(n,i)=1（i<=n）的数的平方和。

用容斥，先用公式$\frac{n(n+1)(2n+1)}{6}$求出1~n的平方和，然后筛出sqrt(n)内的素数，并求出n的所有质因数，然后对于质因数的乘积tot，如果质因数的个数是奇数，就加上$tot^2*(1^2+2^2+3^2……+(n/tot)^2)$，是偶数就减去。

或者用莫比乌斯反演来做

看！代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define MAXN 10000
using namespace std;
typedef long long ll;
ll pri[10010],num=0;
bool vis[10010];
vector<ll>pr;
void init()
{
    ll i,j;
    for(i=2;i<MAXN;i++)
    {
        if(vis[i]==false)pri[num++]=i;
        for(j=0;j<num&&i*pri[j]<MAXN&&i%pri[j]!=0;j++)
            vis[i*pri[j]]=true;
    }
}
void extgcd(ll a,ll b,ll d,ll &x,ll &y)
{
    if(b==0){d=a;x=1;y=0;}
    else{extgcd(b,a%b,d,y,x);y=y-x*(a/b);}
}
ll inverse(ll a,ll p)
{
    ll d,x,y;
    extgcd(a,p,d,x,y);
    return (x%p+p)%p;
}
int main()
{
    init();
    int t;
    ll n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        pr.clear();
        ll xs=inverse(6ll,MOD);
        ll tot=(((n*(n+1))%MOD*(2*n+1))%MOD*xs)%MOD;
        ll temp=n;
        for(int i=0;i<num;i++)
        {
            if(temp%pri[i]==0)
            {
                pr.push_back(pri[i]);
                while(temp%pri[i]==0)
                    temp/=pri[i];
            }
        }
        if(temp>1)pr.push_back(temp);
        int len=pr.size();
        ll ans=0;
        for(int i=1;i<(1<<len);i++)
        {
            int cnt=0;//有几个1
            ll d=1;
            for(int j=0;j<len;j++)
            {
                int temp=i>>j&1;
                if(temp==1)
                {
                    cnt++;d=d*pr[j];
                }
            }
            ll gs=n/d;
            ll g=(((gs*(gs+1))%MOD*(2*gs+1))%MOD*xs)%MOD;
            if(cnt%2==0)ans=(ans-((d*d)%MOD*g)%MOD+MOD)%MOD;
            else ans=(ans+((d*d)%MOD*g))%MOD;
            }
        }
        printf("%lld\n",(tot-ans+MOD)%MOD);
    }
    return 0;
}