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

2820: YY的GCD

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

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

Source

hzwer的图

太懒了不想打公式

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstdio>
 7 #define maxn 10000000
 8 #define ll long long
 9 using namespace std;
10 ll n,m;
11 bool vis[maxn+1];
12 ll prime[maxn+1],u[maxn+1],f[maxn+1],cnt;
13 void pre() {
14     u[1]=1;
15     for(int i=2;i<=maxn;i++) {
16         if(!vis[i]) {prime[++cnt]=i;u[i]=-1;}
17         for(int j=1;j<=cnt&&i*prime[j]<=maxn;j++) {
18             vis[i*prime[j]]=1;
19             if(!(i%prime[j])) {u[i*prime[j]]=0;break;}
20             u[i*prime[j]]=-u[i];
21         }
22     }
23     for(int i=1;i<=cnt;i++) {
24         int tmp=prime[i];
25         for(int j=tmp;j<=maxn;j+=tmp) f[j]+=u[j/tmp];
26     }
27     for(int i=1;i<=maxn;i++) f[i]+=f[i-1];
28 }
29 int T;
30 int main() {
31     pre();scanf("%d",&T);
32     while(T--) {
33         ll ans=0;
34         scanf("%lld%lld",&n,&m);
35         if(n>m) swap(n,m);
36         for(int i=1,j;i<=n;i=j+1) {
37             j=min(n/(n/i),m/(m/i));
38             ans+=(n/i)*(m/i)*(f[j]-f[i-1]);
39         }
40         printf("%lld
",ans);
41     }
42 }

View Code

O(∩_∩)O~ (*^__^*) 嘻嘻…… O(∩_∩)O哈哈~