发个数学题上来大伙儿帮忙瞧瞧

发个数学题上来大家帮忙瞧瞧
我想了一上午，都还没思路。

时间限制：3000 MS
内存限制：65536 KB
Description
平面上有m*n个整点，他们的坐标(x, y)满足1<=x<=m, 1<=y<=n, x,y都是整数。求从原点能看到的点的数量（如果某点与原点的连线上没有其他点，则该点能被原点看到）。 
Input
第一行一个数t（1<=t<=15），表示数据的组数
以下每组数据一行，每行两个数m,n（0<=m, n<=50000）
Output
对于每组数据，输出能被原点看到的点的总数
Sample Input
2
1 1
2 3
Sample Output
1
5

当m==n时，从1~20，可见点数如下：


我本以为数列有规律的，但是也还没找出来。
下边的写法第一会超时，第二内存不够，m,n都是5w的范围。

[解决办法]
引用: 
 
Quote: 引用:

固定x为一常数c，遍历x从1到m
在[1,n]中找到y，使得y和x互质，统计其个数
将所有y和x互质的个数累加，即是答案

y和c互质的个数 = n 减去 y和c的公约数大于1的个数
所以答案为：


谢谢你的回答，但是这个算法是不是有问题，比如m=n=4,互质的个数应该是11个，用你的公式算出来是12个。
这个应该是对的，不过没有考虑重复问题
考虑一下，把重复去掉，应该就行了。
m/n 估计会重复计算