【转】Hdu--4135 Co-prime

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

Source

The Third Lebanese Collegiate Programming Contest

代码：

 1 /*
 2 [a,b] 与n互质的数的个数
 3 
 4 1~b : a1
 5 1~a-1 : a2 
 6 
 7 ans = a1 - a2
 8 
 9 ----> [1,k] 与 n 互质的数的个数
10 
11 ----> num - 与n不互质的数的个数
12 
13 */
14 #include<cstdio>
15 #include<cmath>
16 int p[100000];
17 int ant;
18 void ResolvePrime(int n)        //分解质因数 
19 {
20     int endd = sqrt(n);
21     for (int i = 2 ; i <= endd ; i++)
22     {
23         if (n % i == 0)
24         {
25             p[ant++] = i;
26             while (n % i == 0)
27                 n /= i;
28         }
29     }
30     if (n > 1)
31         p[ant++] = n;
32 }
33 
34 __int64 solve(__int64 a,int n)        //求 1～ a 不与n互质的数的个数 
35 {
36     __int64 ans = 0;
37     for (int i = 1 ; i < ((__int64)1 << ant) ; i++)
38     {
39         __int64 mul = 1;
40         int cnt = 0;
41         for (int j = 0 ; j < ant ; j++)
42         {
43             if (i & ((__int64)1 << j))        //选中 
44             {
45                 cnt++;
46                 mul *= p[j];
47             }
48         }
49         if (cnt & 1)
50             ans += a / mul;
51         else
52             ans -= a / mul;
53     }
54     return ans;
55 }
56 
57 int main()
58 {
59     int T;
60     int n;
61     __int64 a,b;
62     int Case = 1;
63     scanf ("%d",&T);
64     while (T--)
65     {
66         ant = 0;
67         scanf ("%I64d %I64d %d",&a,&b,&n);
68         ResolvePrime(n);
69         printf ("Case #%d: %I64d
",Case++,b-(a-1)-(solve(b,n)-solve(a-1,n)));
70     }
71     return 0;
72 }