[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就不用

 #include<iostream>
 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 using namespace std;
 typedef long long lol;
 lol ans;
 int prime[];
 lol mu[];
 int n,m,d,tot;
 bool vis[];
 void mobius()
 {int i,j;
     mu[]=;
     for (i=;i<=;i++)
     {
         if (vis[i]==)
         {
             tot++;
             prime[tot]=i;
             mu[i]=-;
         }
         for (j=;j<=tot,i*prime[j]<=;j++)
         {
             vis[i*prime[j]]=;
             if (i%prime[j]==)
             {
                 mu[i*prime[j]]=;
                 break;
             }
             mu[i*prime[j]]=-mu[i];
         }
     }
     for (i=;i<=;i++)
     mu[i]+=mu[i-];
 }
 void solve()
 {int i;
     int pos=;
     int r=min(n,m);
     for (i=;i<=r;i=pos+)
     {
         if (n/(n/i)>m/(m/i))
         pos=m/(m/i);
         else pos=n/(n/i);
         ans+=(mu[pos]-mu[i-])*(long long)(n/i)*(long long)(m/i);
     }
 }
 int main()
 {int T;
     cin>>T;
     mobius();
     while (T--)
     {
         scanf("%d%d%d",&n,&m,&d);
         n=n/d;m=m/d;
         ans=;
         solve();
         printf("%lld\n",ans);
     }
 }