hdu4135Co-prime——容斥定理

灰太狼 2022-05-18 00:10 215阅读 0赞

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 15) and (1 <=N <= 10 9).  
**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**  
2  
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  A , B , N 让你找出区间\[A,B\]  \[ A , B \] 内与N  N 互质数的个数  
假设g(n) g ( n )表示从\[1,n\]  \[ 1 , n \] 与n互质数的个数，  
那么

ans=g(B)−g(A−1)  a n s = g ( B ) − g ( A − 1 )

但是我们找  g(n)  g ( n )  比较麻烦，因为找的都是与n互质的数，我们可以反面思考，1到n内与n互质数的个数就等于n减去与n不互质数的个数

假设f(n)  f ( n ) 表示从\[1,n\]  \[ 1 , n \] 与n不互质数的个数  
那么

g(n)=n−f(n)  g ( n ) = n − f ( n )

f(n)  f ( n )  可以根据容斥定理求出来，这样一来，问题就简单化了

--------------------

code:

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    
    ll a[1000000+9],factor[1000],sz;
    
    void p(ll n)
    {
        sz=0;
        memset(factor,0,sizeof(factor));
        for(ll i=2;i*i<=n;i++)
        {
            if(n%i==0)
            {
                factor[sz++]=i;
                while(n%i==0)
                    n/=i;
            }
        }
        if(n!=1)    factor[sz++]=n;
    }
    ll f(ll n)//找 1 ... n 的与 n 不互质的数的个数 
    {
        ll ans=0;
        for(int i=1;i<(1<<sz);i++)
        {
            int cnt=0;
            ll m=1; 
            for(int j=0;j<sz;j++)
                if((i>>j)&1)
                {
                    cnt++;
                    m*=factor[j];
                }
            if(cnt&1)   ans += n/m;
            else        ans -= n/m; 
        }
        return ans;
    }
    
    int main()
    {
        int t;
        ll a,b,n;
        int kase=0; 
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld %lld %lld",&a,&b,&n);
            p(n);
    //      for(int i=0;i<sz;i++)
    //          printf("%lld ",factor[i]);
    //      printf("\n"); 
            ll ans=b-f(b)-(a-1-f(a-1));
            printf("Case #%d: %lld\n",++kase,ans);
        }
        return 0;
    }