hdu4135--Co-prime（欧拉函数+容斥原理） - c++编程基础

Co-prime Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Appoint description:

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

 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互质的个数

分别统计1到a-1中，和1到b中与n互质的数，在相减，求1到m中与n互质的数，先求1到m中与n不互质的数的个数。

求出n分解后的质数个数，用二进制数表示第i个质数的选和不选，得到m内包含的个数，当选了奇数个质数是，统计的结果累加，为偶数个时，减去。

#include 
  
   
#include 
   
     #include 
    
      using namespace std ; #define LL __int64 int prim[1000000] , vis[1000000] , cnt ; void sieve() { memset(vis,0,sizeof(vis)) ; cnt = 0 ; LL i , j ; for(i = 2 ; i <= 1000000 ; i++) { if( !vis[i] ) { prim[cnt++] = i ; for(j = i*i ; j < 1000000 ; j += i) vis[j] = 1 ; } } } LL p[1000] , p_num ; LL f(LL n,LL m) { LL k = n , temp , ans = 0 ; int i , j , num ; for(i = 0 , p_num = 0 ; i < cnt ; i++) { if( k % prim[i] == 0 ) { p[p_num++] = prim[i] ; } while( k % prim[i] == 0 ) { k /= prim[i] ; } if(k == 1) break ; } if( k > 1 ) p[p_num++] = k ; for(i = 1 ; i < (1<