BZOJ 2820 YY问题中，如何运用莫比乌斯反演求解GCD？

本文共计588个文字，预计阅读时间需要3分钟。

题目链接：+BZOJ+2820+限制题+描述：神皇YY无聊完数论后给kAc出了这么一道题。给定N,M，1=x=N，1=y=M且gcd(x,y)为质数的(x,y)有多少对？kAc这种题当然不会了，于是向你请教……多对“

题目链接：
​​​BZOJ 2820 权限题​​

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

题解：
莫比乌斯反演。