首页 > 代码库 > bzoj 2820: YY的GCD

bzoj 2820: YY的GCD

2820: YY的GCD

Time Limit: 10 Sec  Memory Limit: 512 MB

Description

神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种
傻×必然不会了,于是向你来请教……多组输入

Input

第一行一个整数T 表述数据组数接下来T行,每行两个正整数,表示N, M

Output

T行,每行一个整数表示第i组数据的结果

Sample Input

2
10 10
100 100

Sample Output

30
2791

HINT

T = 10000

N, M <= 10000000

 

ans=Σ  Σ μ(T/p) floor(n/T)floor(m/T)

       T p\T

此公式不会看这里 http://www.cnblogs.com/TheRoadToTheGold/p/6606194.html

现在是枚举T、P,肯定TLE

所以继续推

令 f(T)=Σ μ(T/p)  p为素数

             p\T

根据线性筛的思路

当T为素数时 只有p=T,∴f(T)=μ(1)=1

当T不为素数时,

令T=i*prime[j]

对i分解质因数,i=p1^k1*p2^k2*p3^k3……

当i%prime[j]!=0时, f[i]=Σ μ(i/p)=μ(p1^(k1-1)*p2^k*p3^k……)+μ(p1^k1*p2^(k2-1)*p3^k3……)+μ(p1^k1*p2^k2*p3^(k3-1)……)+……

                                    p\i

为了方便表示,令s1=μ(p1^(k1-1)*p2^k*p3^k……)  s2=μ(p1^k1*p2^(k2-1)*p3^k3……)  s3=μ(p1^k1*p2^k2*p3^(k3-1)……)  ……

f[T]=Σ μ(T/p)=μ(s1*prime[j])+μ(s2*prime[j])+μ(s3*prime[j])+……+μ(T/prime[j])

      p\T

                      = μ(prime[j])*(μ(s1)+μ(s2)+μ(s3)+……)+μ(T/prime[j])

                      =μ(prime[j])*f(i)+μ(i)

                      =-f(i)+μ(i)

当i%prime[j]==0时,i分解质因数,其中必有一个pi=prime[j]

∴上面f(T)中每一项中,除最后一项外,前面每一项的prime[j]都可以与si中的1个pi合并为一个,即出现了pi^ki ki>=2 

∴f(T)除最后一项都=0

看最后一项,μ(T/prime[j]),因为T=i*prime[j],所以prime[j]约去

所以最优后一项=μ(i)

综上所述,线性筛时,枚举i

当i为素数时 f(i)=1

当i%prime[j]!=0时,f(i*prime[j])= μ(i)-f(i)

当i%prime[j]   =0时,  f(i*prime[j])=μ(i)

 

为什么这里把T是素数换成了i是素数

因为线性筛的过程,T若是素数,一定可以在某个i时被枚举到

然后i*prime[j]就相当于推导过程中的T

 

#include<cstdio>#include<algorithm>#define N 10000001using namespace std;int t;long long x,y;int prime[N],miu[N],cnt,f[N],sum[N];bool v[N];void pre(){    miu[1]=1;    for(int i=2;i<N;i++)    {        if(!v[i])        {            v[i]=true;            prime[++cnt]=i;            miu[i]=-1;            f[i]=1;        }        for(int j=1;j<=cnt;j++)        {            if(i*prime[j]>N-1) break;            v[i*prime[j]]=true;            if(i%prime[j]==0)            {                miu[i*prime[j]]=0;                f[i*prime[j]]=miu[i];                break;            }            miu[i*prime[j]]=-miu[i];            f[i*prime[j]]=miu[i]-f[i];        }    }    for(int i=1;i<N;i++) sum[i]=sum[i-1]+f[i];}void solve(){    long long k=min(x,y),j,ans=0;    for(long long i=1;i<=k;i=j+1)    {        j=min(x/(x/i),y/(y/i));        ans+=(x/i)*(y/i)*(sum[j]-sum[i-1]);    }    printf("%lld\n",ans);}int main(){    pre();    scanf("%d",&t);    while(t--)    {        scanf("%lld%lld",&x,&y);        solve();    }}

 

元元真厉害\(^o^)/~

我的智商啊~~~~(>_<)~~~~

bzoj 2820: YY的GCD