题目链接：
?pid=2841
题目大意：
给一个含有N*M个点的矩阵，左下角的点为(1，1)，右上角的点为(N，M)，一个人站在
(1，1)点看这些点，在一条直线上，他只能看到最前边的点，后边的点都被挡住看不到了。
那么问题来了：这个人总共能看到多少个点？
思路：
发现一条线上的点，，斜率都是一样的，后边的点都是最前边能看到点的倍数，能被看到的点
都是横纵坐标公约数为1的点，即gcd(x，y) = 1，如果有一个点(x，y)，有一个公约数d，即
gcd(x，y) = d，那么，它就被前边(x/d，y/d)的点挡住了。问题就变求N*M个点中横纵坐标
互质的对数。x的范围为[1，N]，y的范围为[1，M]，我们固定区间[1，M]，从[1，N]中遍历
x，得到x与[1，M]中的数互质的个数，累加起来就是最终结果。
现在问题是求范围[1，M]中与x互质的个数。
这就变成了和HDU4135差不多的问题。先求与x不互质的数的个数，在用x减去就是互质的个数。
与x不互质的数就是[1，M]中n的素因子的倍数。
例如M = 12，x= 30的情况。
30的素因子数为2、3、5。
[1，12]中含有2的倍数的有：(2、4、6、8、10、12) = n/2 = 6个
[1，12]中含有3的倍数的有：(3、6、9、12) = n/3 = 4个
[1，12]中含有5的倍数的有：(5、10) = n/5 = 2个
与x不互质的数个数就是上边三个集合取并集的部分。这里用到了容斥定理，我用的增长的队列数组
来实现容斥定理，具体参考代码。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define LL __int64using namespace std;LL Q[100010],factor[110000],num;void Divid(LL n){num = 0;for(LL i = 2; i*i <= n; ++i){if(n%i==0){while(n%i==0){n /= i;}factor[num++] = i;}}if(n != 1)factor[num++] = n;}LL solve(LL n) //互斥定理{LL k,t,ans;t = ans = 0;Q[t++] = -1;for(LL i = 0; i < num; ++i){k = t;for(LL j = 0; j < k; ++j)Q[t++] = -1*Q[j]*factor[i];}for(LL i = 1; i < t; ++i)ans += n/Q[i];return ans;}int main(){int T;scanf("%d",&T);while(T–){LL H,W,ans;scanf("%I64d%I64d",&H,&W);if(H < W)swap(H,W);ans = H;for(LL i = 2; i <= W; ++i){Divid(i);ans += (H – solve(H));}printf("%I64d\n",ans);}return 0;}
一个有信念者所开发出的力量，大于99个只有兴趣者。
