HDU4135 Co-prime【容斥原理】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4135

题目大意：

给一个区间[a，b]，从区间[a，b]中找出共有多少个数是与n互质的。

思路：

欧拉函数得到的是小于n与n互质的个数，这里是个区间。由于区间较大，不可能对[a，b]进行遍历，

考虑计算区间[1，a-1]中与n互质的个数num1，[1，b]中与n互质的个数num2，最终结果就是两者

相减的结果。

现在考虑如何计算区间[1，m]中n互质的个数num，num等于 (m - 与n不互质的个数)。

与n不互质的数就是[1，m]中n的素因子的倍数。

例如m = 12，n = 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个

与n不互质的数个数就是上边三个集合取并集的部分。这里用到了容斥定理，我用的增长的队列数组

来实现容斥定理，具体参考代码。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define LL __int64
using namespace std;

LL Q[100010],factor[110],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,kase = 0;
    scanf("%d",&T);
    while(T--)
    {
        LL a,b,n;
        scanf("%I64d%I64d%I64d",&a,&b,&n);
        Divid(n);
        LL ans = b - solve(b) - (a-1-solve(a-1));
        printf("Case #%d: %I64d\n",++kase,ans);
    }

    return 0;
}

原文：http://blog.csdn.net/lianai911/article/details/44650669