hdu4135--Co-prime（歐拉函數+容斥原理）

hdu4135--Co-prime（歐拉函數+容斥原理）

Co-prime Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Appoint description: System Crawler (2015-01-07)

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<