首页 > 代码库 > 【BZOJ2820】YY的GCD [莫比乌斯反演]

【BZOJ2820】YY的GCD [莫比乌斯反演]

2024-09-12 16:17:34   219人阅读

YY的GCD

Time Limit: 10 Sec  Memory Limit: 512 MB
[Submit][Status][Discuss]

Description

　　求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对k。

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

Source

　　技术分享

Code

技术分享
 1 #include<iostream>   2 #include<string>   3 #include<algorithm>   4 #include<cstdio>   5 #include<cstring>   6 #include<cstdlib>   7 #include<cmath> 8 using namespace std;  9 typedef long long s64;10    11 const int ONE = 10000005;12      13 int T;14 int n,m;15 bool isp[ONE];16 int prime[700005],p_num;17 int miu[ONE],sum[ONE];18 s64 Ans;19   20 int get() 21 {22         int res=1,Q=1;  char c;23         while( (c=getchar())<48 || c>57)24         if(c==‘-‘)Q=-1;25         if(Q) res=c-48; 26         while((c=getchar())>=48 && c<=57) 27         res=res*10+c-48; 28         return res*Q; 29 }30    31 void Getmiu(int MaxN)32 {33         miu[1] = 1;34         for(int i=2; i<=MaxN; i++)35         {36             if(!isp[i])37                 prime[++p_num] = i, miu[i] = -1;38             for(int j=1; j<=p_num, i*prime[j]<=MaxN; j++)39             {40                 isp[i * prime[j]] = 1;41                 if(i % prime[j] == 0)42                 {43                     miu[i * prime[j]] = 0;44                     break;45                 }46                 miu[i * prime[j]] = -miu[i];47             }48         }49         for(int j=1; j<=p_num; j++)50             for(int i=1; i*prime[j]<=MaxN; i++)51                 sum[i * prime[j]] += miu[i];52         for(int i=1; i<=MaxN;i++)53             sum[i] += sum[i-1]; 54 }55  56 void Solve()57 {58         n=get();    m=get();59         if(n > m) swap(n,m);60         Ans = 0;61         for(int i=1, j=0; i<=n; i=j+1)62         {63             j = min(n/(n/i), m/(m/i));64             Ans += (s64) (n/i) * (m/i) * (sum[j] - sum[i-1]);65         }66         printf("%lld\n",Ans);67 }68  69 int main()70 {71         Getmiu(ONE-1);72         T=get();73         while(T--)74             Solve();75 }
View Code

 

【BZOJ2820】YY的GCD [莫比乌斯反演]


联系
我们