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

大佬的题解还是弱啊orz

/*

莫比乌斯.

最后用除法分块..

筛莫比乌斯函数部分:

显然每个素数直接计算mu[i]=-1.

我们知道莫比乌斯函数值是(-1)^k,k是互异质数的个数.

对于一个合数x,令它质因子的最小的那个为p1,

则有x=p1*t1,另设一个与异于p1的质因子为p2.

则有p1*t1=p2*t2.

因为p1与p2互素,所以p2|t1,p1|t2.

所以当i枚举到t2时,因为p1|t2,所以退出

**有一个疑问:就是如果有一个数x1>x,那直接退出以后是不是会影响x1函数值的计算???数学不好没证出来orz**

假如有一个x1=t1*p,且p是x1最大的质因数.

当i枚举到t1时,计算一下x的函数值.

所以我们保证算的每一个合数的莫比乌斯函数的时候

都是在最后一个计算素数的时候的

即每个函数值都只计算了一次.

复杂度是O(n)哒.

*/

#include<iostream>

#include<cstdio>

#define MAXN 10000001

#define LL long long

using namespace std;

int mu[MAXN],pri[MAXN],tot,g[MAXN],sum[MAXN],last;

LL ans,n,m;

bool vis[MAXN];

void pre()

{

    mu[1]=1;

    for(int i=2;i<=MAXN-1;i++)

    {

        if(!vis[i]) pri[++tot]=i,mu[i]=-1,g[i]=1;

        for(int j=1;j<=tot&&i*pri[j]<=MAXN-1;j++)

        {

            vis[i*pri[j]]=true;

            if(i%pri[j]) mu[i*pri[j]]=-mu[i],g[i*pri[j]]=mu[i]-g[i];

            else {

                mu[i*pri[j]]=0;g[i*pri[j]]=mu[i];break;

            }

        }

    }

    for(int i=1;i<=MAXN-1;i++) sum[i]=sum[i-1]+g[i];

}

int main()

{

    int t,x,y;pre();

    scanf("%d",&t);

    while(t--)

    {

        scanf("%lld%lld",&n,&m);

        if(n>m) swap(n,m);

        ans=0;

        for(LL i=1;i<=n;i=last+1)

        {

            last=min(n/(n/i),m/(m/i));

            ans+=(n/i)*(m/i)*(sum[last]-sum[i-1]);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

Bzoj 2820: YY的GCD(莫比乌斯反演+除法分块)

最新文章

热门文章