Description
CX老湿经常被人黑，被黑得多了，自己也就麻木了。于是经常听到有人黑他，他都会深情地说一句：禽兽啊！
一天CX老湿突发奇想，给大家出了一个难题，并且声称谁能够准确地回答出问题才能继续黑他，否则他就要反击了。
这个难题就是：
给出两个数p和q，接下来q个询问，每个询问给出两个数A和B，请分别求出：
一、有多少个有序数对（x，y）满足1<=x<=A，1<=y<=B，并且gcd（x，y）为p的一个约数；
二、有多少个有序数对（x，y）满足1<=x<=A，1<=y<=B，并且gcd（x，y）为p的一个倍数。
Input
只有一组测试数据。
第一行两个数：p和q。（1<p<10^7 ，1<q<1000。）
接下来有q行，每行两个数A和B。（1<A,B<10^7）
Output
输出共q行。每行两个数。用空格隔开。
分别表示题目描述中的两个对应的答案。
(x,y)=(2,3)和(x,y)=(3,2)被视为两个不同有序数对哦！
Sample Input
6 3 8 8 15 32 13 77
Sample Output
58 1 423 10 883 24
HINT
对于64位整型请用lld，或者cin，cout。T_T
CSU_LQ
Source
题解：
1.对于第二个答案，就是(a/p)*(b/p);
2.对于第一个答案，要用到莫比乌斯函数，比如如统计gcd(x,y)=3的情况，(假设p=10),将会有3,6,9这三种情况，如果算(10/3)*(10/3)的话将会有重复计算的；
如果在上面乘以莫比乌斯系数的话就不会了，他们的系数分别为 1，-1,-1，则结果就是：1*(10/3)*(10/3)-1*(10/6)*(10/6)-1*(10/9)*(10/9);
所以要对莫比乌斯系数打表，比赛的时候，一个大神用一个神码A了这个题；无比的膜拜！！！OTL
分享一个：
#include<cstdio>
#define maxn 10000001
#define ll long long
using namespace std;
int a,b,cnt[maxn];
ll getans(int l,int r)
{
if(l>r)return ;
if(a/l==a/r&&b/l==b/r)
return (ll)(cnt[r]-cnt[l-])*(a/l)*(b/l);
return getans(l,(l+r)/)+getans((l+r)/+,r);
} int main()
{
int p,q;
scanf("%d%d",&p,&q);
for(int i=;i<maxn;i++)
{
if(p%i==)cnt[i]++;
if(cnt[i]!=)for(int j=i+i;j<maxn;j+=i)
cnt[j]-=cnt[i];
cnt[i]+=cnt[i-];
}
while(q--)
{
scanf("%d%d",&a,&b);
printf("%lld %d\n",getans(,maxn-),(a/p)*(b/p));
}
return ;
}