题目。。大概就是有个m*n个点的矩形从(1,1)到(m,n)，问从(0,0)出发直线看过去最多能看到几个点。
如果(0,0)->(x,y)和(0,0)->(x',y')两个向量平行，那后面的那个点就看不到了。
因此给出一个点(x,y)，判断它能否被看到，就是是否能找到一个大于1的k，使k|x且k|y。
这样，问题就能转变为有几个点的x、y找不到公约数，即有几对x、y，满足x和y互质。
可以通过枚举x，看有几个y与其互质累加。这样问题就又变成，区间有几个数与某个数互质，经典的容斥问题HDU4135。
时间复杂度方面，1 ≤ m, n ≤ 100000，前7个素数乘积就超过100000了，即一个数最多有6个质因数，大概估个非常松的上界$O((\sqrt m+2^6)n)$，应该是妥妥的。
#include<cstdio>
#include<cstring>
using namespace std;
int prime[],pn;
int getCnt(int n,int m){
pn=;
for(int i=; i*i<=m; ++i){
if(m%i) continue;
while(m%i==) m/=i;
prime[pn++]=i;
}
if(m!=) prime[pn++]=m;
int res=;
for(int i=; i<(<<pn); ++i){
int tmp=,cnt=;
for(int j=; j<pn; ++j){
if(((i>>j)&)==) continue;
tmp*=prime[j];
++cnt;
}
if(cnt&) res+=n/tmp;
else res-=n/tmp;
}
return n-res;
}
int main(){
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
long long res=;
for(int i=; i<=n; ++i){
res+=getCnt(m,i);
}
printf("%lld\n",res);
}
return ;
}