当前位置：网站首页>HDU 4135: Co-prime (the principle of inclusion and exclusion)

HDU 4135: Co-prime (the principle of inclusion and exclusion)

2022-08-10 11:52:00 【51CTO】


Co-prime


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


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 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
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    •

 


Sample Output 


      
      

       
       Case #1: 5
       
       
Case #2: 10
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    •

思路：Usually we ask1-ｎ中与ｎThe number of coprime numbers is calculated by Euler's function！ 但如果ｎBigger or bigger１～ｍ中与ｎThe number of coprime numbers and so on,If you want to be more time efficient, you should use the principle of inclusion and exclusion！

容斥：先对n分解质因数,Record each prime factor separately, Then the number of non-coprime factors with a prime factor in the required interval is n / r(i),假设r(i)是ra prime factor of Suppose there are only three prime factors, The total number of non-coprime should be p1+p2+p3-p1*p2-p1*p3-p2*p3+p1*p2*p3, and the principle of inclusion and exclusion,You can turn to Baidu Encyclopedia to view related content pi代表n/r(i),That is, the number of numbers that are not coprime to a prime factor ,when there are more prime factors, It can be solved with state compression,二进制位上是1Indicates that the prime factor is taken in. 如果有奇数个1,就相加,Otherwise, it is subtracted.



AC代码：

      
      

       
       #include<stdio.h>
       
       

       
       #include<string.h>
       
       

       
       #include<iostream>
       
       

       
       #include<vector>
       
       

       
       typedef 
       
       __int64 
       
       LL;
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       vector
       
       <
       
       LL
       
       >
       
       prime;
       
       

       
       void 
       
       jprime(
       
       LL 
       
       n)   
       
       //分解质因子
       
       
{
       
       
    
       
       for(
       
       LL 
       
       i
       
       =
       
       2; 
       
       i
       
       *
       
       i
       
       <=
       
       n; 
       
       i
       
       ++)
       
       
        
       
       if(
       
       n
       
       %
       
       i
       
       ==
       
       0)
       
       
        {
       
       
            
       
       prime.
       
       push_back(
       
       i); 
       
       //质因子
       
       
            
       
       while(
       
       n
       
       %
       
       i
       
       ==
       
       0)
       
       
                
       
       n
       
       /=
       
       i;
       
       
        }
       
       
    
       
       if(
       
       n
       
       >
       
       1)
       
       prime.
       
       push_back(
       
       n);
       
       
}
       
       

       
       

       
       LL 
       
       solve(
       
       LL 
       
       a,
       
       LL 
       
       b,
       
       LL 
       
       n)    
       
       //[a,b]中与n互质的数的个数
       
       
{
       
       
    
       
       LL 
       
       sum
       
       =
       
       0;
       
       
    
       
       LL 
       
       size
       
       =
       
       prime.
       
       size();
       
       
    
       
       for(
       
       LL 
       
       msk
       
       =
       
       1; 
       
       msk
       
       <(
       
       1
       
       <<
       
       size); 
       
       msk
       
       ++) 
       
       //共有2^size种组合情况
       
       
    {
       
       
        
       
       LL 
       
       mult
       
       =
       
       1,
       
       bits
       
       =
       
       0;
       
       
        
       
       for(
       
       LL 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       size; 
       
       i
       
       ++)    
       
       //枚举每一种情况
       
       
        {
       
       
            
       
       if(
       
       msk
       
       &(
       
       1
       
       <<
       
       i))  
       
       //If within the current judgment
       
       
            {
       
       
                
       
       ++
       
       bits;
       
       
                
       
       mult
       
       *=
       
       prime[
       
       i];
       
       
            }
       
       
        }
       
       
        
       
       LL 
       
       cur
       
       =
       
       b
       
       /
       
       mult
       
       -(
       
       a
       
       -
       
       1)
       
       /
       
       mult;   
       
       //中间结果
       
       
        
       
       if(
       
       bits
       
       &
       
       1)
       
       sum
       
       +=
       
       cur;
       
       
        
       
       else 
       
       sum
       
       -=
       
       cur;
       
       
    }
       
       
    
       
       return 
       
       b
       
       -
       
       a
       
       -
       
       sum
       
       +
       
       1;
       
       
}
       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       LL 
       
       T;
       
       
    
       
       scanf(
       
       "%I64d",
       
       &
       
       T);
       
       
    
       
       for(
       
       LL 
       
       t
       
       =
       
       1; 
       
       t
       
       <=
       
       T; 
       
       t
       
       ++)
       
       
    {
       
       
        
       
       LL 
       
       a,
       
       b,
       
       n;
       
       
        
       
       scanf(
       
       "%I64d%I64d%I64d",
       
       &
       
       a,
       
       &
       
       b,
       
       &
       
       n);
       
       
        
       
       prime.
       
       clear();
       
       
        
       
       jprime(
       
       n);
       
       
        
       
       printf(
       
       "Case #%I64d: %I64d\n",
       
       t,
       
       solve(
       
       a,
       
       b,
       
       n));
       
       
    }
       
       
    
       
       return 
       
       0;
       
       
}
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    • 
       
       
  • 29.
    • 
       
       
  • 30.
    • 
       
       
  • 31.
    • 
       
       
  • 32.
    • 
       
       
  • 33.
    • 
       
       
  • 34.
    • 
       
       
  • 35.
    • 
       
       
  • 36.
    • 
       
       
  • 37.
    • 
       
       
  • 38.
    • 
       
       
  • 39.
    • 
       
       
  • 40.
    • 
       
       
  • 41.
    • 
       
       
  • 42.
    • 
       
       
  • 43.
    • 
       
       
  • 44.
    • 
       
       
  • 45.
    • 
       
       
  • 46.
    • 
       
       
  • 47.
    • 
       
       
  • 48.
    • 
       
       
  • 49.
    • 
       
       
  • 50.
    • 
       
       
  • 51.
    • 
       
       
  • 52.
    • 
       
       
  • 53.
    • 
       
       
  • 54.
    •
原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/222/202208101049385558.html

边栏推荐

猜你喜欢

随机推荐