BZOJ-2820: YY的GCD

[文章目录]

Description

就是求一个p为质数。多组输入<= n,m<=

考虑犹如[gcd(i,j)==1]一样化简;=> (p为质数)

又因为

=>(p为质数)

考虑每个被累加的次数=>

我们发现右面次数可以求出,考虑左边。只需要求出来一个前缀和就好了。不妨设T=p*d.那么只需要求出来

%%%EdwardFrog,暴力枚举质数更新答案(据说均摊复杂度大概是O(n)的)。

不考虑这种玄学算法,我们快筛。设这个函数为f(T)
如果i%pri==0:f(i*pri)中,我们发现当中p不为pri的时候,都为0,当p为pri的时候才有可能不为0,才能够对答案有贡献.那么答案就是:

第一个公式:if(i%pri==0) f(i*pri)=

考虑另一种情况:i%pri!=0,我们发现中当p不为pri的时候,T都相当于多乘了个pri。那么,所有的都相当于乘上一个-1.当p为pri的时候,这个东西等于

第二个公式:else f(i*pri)=-f(i)+

快筛吧。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 10000000
int T,n,m,cnt;
int mu[10001000],pri[701000];
int sum[10001000];
bool v[10001000];
void initialize()
{
    mu[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!v[i]) pri[++cnt]=i,mu[i]=-1,sum[i]=1;
        for(int j=1;j<=cnt&&i*pri[j]<=N;j++)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                mu[i*pri[j]]=0;
                sum[i*pri[j]]=mu[i];
                break;
            }
            else
            {
                mu[i*pri[j]]=mu[i]*-1;
                sum[i*pri[j]]=-sum[i]+mu[i];
            }
        }
    }
    for(int i=1;i<=N;i++)
        sum[i]+=sum[i-1];
}

ll query(int x,int y)
{
    if(x>y) swap(x,y);
    int b=1,e;
    ll re=0;
    while(b<=x)
    {
        e=min(x,min(x/(x/b),y/(y/b)));
        re+=1ll*(sum[e]-sum[b-1])*(x/b)*(y/b);
        b=e+1;
    }
    return re;
}
int read()
{
    char ch=getchar(); int re=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}
int main()
{
    initialize();
    scanf("%d",&T);
    while(T--)
    {
        n=read(); m=read();
        printf("%lld\n",query(n,m));
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注