HDU 4135 Co-prime (容斥原理、分解质因数）

Co-prime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6224 Accepted Submission(s): 2506

Problem Description

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Input

The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 10¹⁵) and (1 <=N <= 10⁹).

Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

Sample Input

1 10 2

3 15 5

Sample Output

Case #1: 5

Case #2: 10

Hint

In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

题意：求区间[a,b]内与n互质的的数的数量

第一步：求n的质因子

第二步：通过求与n不互质的数的数量，得到与n互质的数的数量；

例：

m=12,n=30.

第一步：求出n的质因子：2,3,5；

第二步：[1,m]中是n的质因子的倍数的数就不互质(2,4,6,8,10,12)->m/2 6个 (3,6,9,12)->m/3 4个, (5,10)->m/5 2个。

答案显然不是全加起来。利用容斥原理去重公式：m/2+m/3+m/5-m/(2*3)-m/(2*5)-m/(3*5)+m/(2*3*5)。除数是奇数的时候加，是偶数的时候减。

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
vector<int>Q;

void init(int n)//求质因子；
{
    Q.clear();
    for(int i=2; i*i<n; i++)//这里是i*i<n,不是i<n;
    {
        if(n%i==0)
        {
            Q.push_back(i);
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        Q.push_back(n);
}
long long fun(long long a)
{
    long long ans=0,val,cnt;
    for(int i=1; i<(1<<Q.size()); i++)//用二进制来1,0来表示第几个素因子是否被用到,如m=3，三个因子是2,3,5，则i=3时二进制是011，表示第2、3个因子被用到
    {
        val=1;
        cnt=0;
        for(int j=0; j<Q.size(); j++)
        {
            if(i&(1<<j))//判断第几个因子目前被用到
            {
                val*=Q[j];
                cnt++;
            }
        }
        if(cnt&1)//容斥原理，奇加偶减
            ans+=a/val;
        else
            ans-=a/val;
    }
    return a-ans;
}
int main()
{
    int t,cas=0;
    long long  a,b,n;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>n;
        init(n);
        long long ans=fun(b)-fun(a-1);
        cout<<"Case #"<<++cas<<": "<<ans<<endl;
    }
    return 0;
}