[POI2007]ZAP-Queries

题目描述

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 , and , find the number of integer pairs satisfying the following conditions:

,,, where is the greatest common divisor of and ".

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 (),denoting the number of queries.

The following lines contain three integers each: , and (), separated by single spaces.

Each triplet denotes a single query.

输出格式：

Your programme should write lines to the standard output. The 'th line should contain a single integer: theanswer to the 'th query from the standard input.

输入输出样例

输入样例#1：

2
4 5 2
6 4 3

输出样例#1：

3
2
题解：莫比乌斯反演+分块
其实我写过一边博客上的题跟这个几乎一摸一样，而且这个还不要容斥
在这里偷个懒，贴出题目 [HAOI2011]Problem b
本题卡常数，所以能不用long long就不用

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 typedef long long lol;
 7 lol ans;
 8 int prime[50001];
 9 lol mu[50001];
10 int n,m,d,tot;
11 bool vis[50001];
12 void mobius()
13 {int i,j;
14     mu[1]=1;
15     for (i=2;i<=50000;i++)
16     {
17         if (vis[i]==0)
18         {
19             tot++;
20             prime[tot]=i;
21             mu[i]=-1;
22         }
23         for (j=1;j<=tot,i*prime[j]<=50000;j++)
24         {
25             vis[i*prime[j]]=1;
26             if (i%prime[j]==0)
27             {
28                 mu[i*prime[j]]=0;
29                 break;
30             }
31             mu[i*prime[j]]=-mu[i];
32         }
33     }
34     for (i=1;i<=50000;i++)
35     mu[i]+=mu[i-1];
36 }
37 void solve()
38 {int i;
39     int pos=1;
40     int r=min(n,m);
41     for (i=1;i<=r;i=pos+1)
42     {
43         if (n/(n/i)>m/(m/i))
44         pos=m/(m/i);
45         else pos=n/(n/i);
46         ans+=(mu[pos]-mu[i-1])*(long long)(n/i)*(long long)(m/i);
47     }
48 }
49 int main()
50 {int T;
51     cin>>T;
52     mobius();
53     while (T--)
54     {
55         scanf("%d%d%d",&n,&m,&d);
56         n=n/d;m=m/d;
57         ans=0;
58         solve();
59         printf("%lld
",ans);
60     }
61 }