HDU4135 Co-prime（容斥原理）

题意：

寻找（a，b）中与n互质的数的个数

要点：

参考博客点击打开链接，求互质一般都是用容斥原理。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
_int64 a[1000], num;void init(_int64 n) //先求n的质因子
{int i;num = 0;for (i = 2; i*i <= n; i++){if (n%i == 0){a[num++] = i;while (n%i == 0)n = n / i;  //将n化简为没有i因子的值}}if (n > 1)a[num++] = n;//自己本身也是因子
}
_int64 number(_int64 m)//找出前m中有多少个与n互质的数
{_int64 que[10000], i, j, k, t = 0, sum = 0;que[t++] = -1;				//一开始que[0]为-1，使后面单个因子的是正的for (i = 0; i < num; i++){k = t;for (j = 0; j < k; j++)que[t++] = que[j] * a[i] * (-1);//一个个求出分子，奇数时为+，偶数是为-}for (i = 1; i < t; i++)sum += m / que[i];return sum;
}int main()
{int t;scanf("%d", &t);for (int i = 1; i <= t;i++){_int64 a, b, n;scanf("%I64d%I64d%I64d", &a, &b, &n);init(n);_int64 sum = b - number(b) - (a - 1 - number(a - 1));//这里注意下界要-1printf("Case #%d: %I64d\n", i,sum);}return 0;
}