Loading...

洛谷P4450 双亲数

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

$NOIP$后康复训练

题目让你求$\sum_{i=1}^a\sum_{j=1}^n(gcd(i,j)==d)(a<b)$

等价于求$\sum_{i=1}^{\frac{a}{d}}\mu(i)\times\lfloor \frac{a}{id}\rfloor \lfloor \frac{b}{id}\rfloor$,很好推导,前面莫比乌斯反演那篇文章里写了

然后前面前缀和后面整除分块

#include <bits/stdc++.h>
using namespace std;
int prime[200020],cnt,mu[1000010],vis[1000010],a,b,d;
void shai()
{
    mu[1]=1;
    for(int i=2;i<=a;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=a;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>>a>>b>>d;
    a/=d;
    b/=d;
    if(a>b)
    {
        swap(a,b);
    }
    shai();
    long long ans=0;
    for(int i=1;i<=a;i++)
    {
        int l=min(a/(a/i),b/(b/i));
        ans+=(long long)(mu[l]-mu[i-1])*(a/i)*(b/i);
        i=l;
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名