题目描述
Byteasar the Cryptographer works on breaking the code of BSA (Byteotian Security Agency). He has alreadyfound out that whilst deciphering a message he will have to answer multiple queries of the form"for givenintegers aa, bb and dd, find the number of integer pairs (x,y)(x,y)satisfying the following conditions:
1le xle a1≤x≤a,1le yle b1≤y≤b,gcd(x,y)=dgcd(x,y)=d, where gcd(x,y)gcd(x,y) is the greatest common divisor of xxand yy".
Byteasar would like to automate his work, so he has asked for your help.
TaskWrite a programme which:
reads from the standard input a list of queries, which the Byteasar has to give answer to, calculates answers to the queries, writes the outcome to the standard output.
FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。
输入输出格式
输入格式：
The first line of the standard input contains one integer nn (1le nle 50 0001≤n≤50 000),denoting the number of queries.
The following nn lines contain three integers each: aa, bb and dd(1le dle a,ble 50 0001≤d≤a,b≤50 000), separated by single spaces.
Each triplet denotes a single query.
输出格式：
Your programme should write nn lines to the standard output. The ii'th line should contain a single integer: theanswer to the ii'th query from the standard input.
输入输出样例
2
4 5 2
6 4 3
3 2
这个算是一个反演的入门题
直接套板子也行qwq
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 long long read()
5 {
6 long long x=0,f=1; char c=getchar();
7 while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
8 while(isdigit(c)){x=x*10+c-'0';c=getchar();}
9 return x*f;
10 }
11 const int N=50000+100;
12 const int M=50000;
13 int cnt_p,prime[N],mu[N];
14 bool noPrime[N];
15 void GetPrime(int n)
16 {
17 noPrime[1]=true,mu[1]=1;
18 for(int i=2;i<=n;i++)
19 {
20 if(noPrime[i]==false)
21 prime[++cnt_p]=i,mu[i]=-1;
22 for(int j=1;j<=cnt_p and i*prime[j]<=n;j++)
23 {
24 noPrime[i*prime[j]]=true;
25 if(i%prime[j]==0)
26 {
27 mu[i*prime[j]]=0;
28 break;
29 }
30 mu[i*prime[j]]=mu[i]*mu[prime[j]];
31 }
32 }
33 }
34 long long pre_mu[N];
35 int main()
36 {
37 GetPrime(M);
38 for(int i=1;i<=M;i++)
39 pre_mu[i]=pre_mu[i-1]+mu[i];
40
41 int T=read();
42 for(;T>0;T--)
43 {
44 long long a=read(),b=read(),x=read();
45
46 long long ans=0;
47 if(a>b) swap(a,b);
48 a/=x,b/=x;
49 for(int l=1,r;l<=a;l=r+1)
50 {
51 r=min(a/(a/l),b/(b/l));
52 ans+=(pre_mu[r]-pre_mu[l-1])*(a/l)*(b/l);
53 }
54
55 printf("%lld
",ans);
56 }
57 return 0;
58 }