BZOJ-2820: YY的GCD

Description

就是求一个$\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)==p]$p为质数。多组输入<=$10^5$ n,m<=$10^7$

考虑犹如[gcd(i,j)==1]一样化简；=> $\sum_{p=2}^n$(p为质数)$\sum_{i=1}^{n/p}\sum_{j=1}^{m/p} [gcd(i,j)==1]$

又因为$\sum_{d|n} \mu(d) ==1(n=1) || ==0 (n!=1)$

=>$\sum_{p=1}^n$(p为质数)$\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}\sum_{d|gcd(i,j)} \mu(d)$

考虑每个$\mu(d)$被累加的次数=>$\sum_{d=1}^{min(n/p,m/p)}\mu(d)*\lfloor n/(p*d)\rfloor * \lfloor m/(p*d)\rfloor$

我们发现右面次数可以$2*\sqrt n$求出，考虑左边。只需要求出来一个前缀和就好了。不妨设T=p*d.那么只需要求出来$\sum_{p|T}^{T,p is prime}\mu(T/p)$

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

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

第一个公式：if(i%pri==0) f(i*pri)=$\mu(i)$

考虑另一种情况：i%pri!=0，我们发现$\sum_{p|T}^{T,p is prime}\mu(T/p)$中当p不为pri的时候，T都相当于多乘了个pri。那么，所有的$\mu(T/p)$都相当于乘上一个-1.当p为pri的时候，这个东西等于$\mu(i)$

第二个公式：else f(i*pri)=-f(i)+$\mu(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;
}