HDU 4135 Co-prime Euler+反発定理

10679 ワード

Co-prime
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 935    Accepted Submission(s): 339
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
 
Sample Output
 
Case #1: 5
Case #2: 10
 1 /*

 2   :   [A,B],   N     。

 3 

 4       :1. [A,B],   

 5               [1,B]  N      

 6                 

 7               [1,A-1]  N     。

 8                       [1,K]    。

 9     2. [1,K]  N          K    [1,K]  N  

10       gcd(N,k1)>1   。

11          ,   N     。       ??

12 13 14            ,         ,          。

15                            ,          。

16     3.              。

17           m=12,n=30

18        :  n    :2,3,5;

19        :(1,m)  n             

20     (2,4,6,8,10)->n/2  6 ,(3,6,9,12)->n/3  4 ,(5,10)->n/5  2 。

21                        :6+4+2=12  ,

22             ,          ,

23 24        :            ,    :n/2+n/3+n/5-n/(2*3)-n/(2*5)-n/(3*5)+n/(2*3*5).

25        :        ?

26                  :dfs(  ),    ,          !

27              :n             ,n             。

28                     :            -1            !

29 */

30 

31 #include<stdio.h>

32 #include<string.h>

33 #include<stdlib.h>

34 

35 __int64 Que[100001];

36 __int64 f[100],len;

37 void Euler(__int64 n)//     ,   f[]

38 {

39     __int64 i;

40     len=0;

41     for(i=2;i*i<=n;i++)

42     {

43         if(n%i==0)

44         {

45             while(n%i==0)

46             n=n/i;

47             f[++len]=i;

48         }

49     }

50     if(n!=1)

51     f[++len]=n;

52 }

53 

54 __int64 Capticy(__int64 num)       

55 {

56     __int64 i,j,t=0,k,sum=0;

57     Que[t++]=-1;

58     for(i=1;i<=len;i++)

59     {

60         k=t;

61         for(j=0;j<k;j++)

62             Que[t++]=-1*Que[j]*f[i];

63     }

64     for(i=1;i<t;i++)

65     sum=sum+num/Que[i];

66     return sum;

67 }

68 

69 int main()

70 {

71     __int64 T,A,B,N,i,k;

72     while(scanf("%I64d",&T)>0)

73     {

74         for(i=1;i<=T;i++)

75         {

76             scanf("%I64d%I64d%I64d",&A,&B,&N);

77             Euler(N);

78             k=B-Capticy(B)-(A-1-Capticy(A-1));

79             printf("Case #%I64d: %I64d
",i,k); 80 } 81 } 82 return 0; 83 }