Loading...

洛谷P2398 GCD SUM&&P1390 公约数的和

check评论:0 条 remove_red_eye浏览量:360 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-01

这两道题基本一样的啊...

那就说一下前者的做法吧

这道题就是让你求$\sum_{d=1}^n\sum_{i=1}^{n}\sum_{j=1}^n(gcd(i,j)=d)$

把式子改为$\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}(gcd(i,j)=1) $,求和的时候我们乘上$d$即可

然后就是莫比乌斯反演基本套路,后面那一截$\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor}(gcd(i,j)=1)$就相当于$\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{id}\rfloor\lfloor\frac{n}{jd}\rfloor$

然后枚举$n$,后面整除分块,时间复杂度大概是$O(n\sqrt n)$?

qwq

#include <bits/stdc++.h>
using namespace std;
int mu[2000010],prime[400020],cnt,vis[2000010],n,m;
void shai()
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
        mu[i]+=mu[i-1];
    }
}
int main()
{
    cin>>n;
    shai();
    m=n;
    unsigned long long ans=0;
    for(int i=1;i<=m;i++)
    {
        n=m;
        n/=i;
        unsigned long long perans=0;
        for(int j=1;j<=n;j++)
        {
            int l=(n/(n/j));
            perans+=(unsigned long long)(mu[l]-mu[j-1])*(unsigned long long)(n/j)*(unsigned long long)(n/j);
            j=l;
        } 
        perans*=(unsigned long long)i;
        ans+=perans;
    }
    cout<<ans;
}

后者差不多,改改就行

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名