莫比乌斯反演 BZOJ 2820

2022-04-04 09:27:18

莫比乌斯反演真（TMD）难学。我自看了好长时间。

BZOJ 2820: YY的GCD

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 1384 Solved: 718

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

 typedef long long ll;

 #include<iostream>

 using namespace std;

 #include<cstdio>

 #include<cstring>

 const int N=;

 bool IS_prim[N+];

 int prim[N+],cnt=,mu[N+],g[N+],sum[N+];

 int T;ll n,m;

 void get_prim()

 {

      cnt=;

      memset(IS_prim,true,sizeof(IS_prim));

      mu[]=;IS_prim[]=false;

      for(int i=;i<N;++i)

      {

          if(IS_prim[i])

          {

              prim[cnt++]=i;

              mu[i]=-;g[i]=;

          }

          for(int j=;j<cnt&&i*prim[j]<N;++j)

          {

              IS_prim[i*prim[j]]=false;

              if(i%prim[j])

              {

                  mu[i*prim[j]]=-mu[i];

                  g[i*prim[j]]=mu[i]-g[i];

              }

              else

              {

                  mu[i*prim[j]]=;

                  g[i*prim[j]]=mu[i];

                  break;

              }

          }

          sum[i]=sum[i-]+g[i];

      }

 }

 int main()

 {

     get_prim();

     scanf("%d",&T);

     while(T--)

     {

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

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

         ll ans=;

         for(int i=,last;i<=n;i=last+)

         {

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

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

         }

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

     }

     return ;

 }

码农公寓