hdu 2588 오랫동안 수 논 제 를 풀 었 습 니 다.

GCD
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 605    Accepted Submission(s): 268
Problem Description
The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.
 
Input
The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.
 
Output
For each test case,output the answer on a single line.
 
Sample Input

   
   
   
   

    
    
    
    3
1 1
10 2
10000 72
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
6
260
   
   
   
   

/*
      ：     case    
	  n m         1 n   n      m       


    ：
      n     m    k            n/k phi(    )    n/k   n/k     
        n/k      n/k        n/k       k         n    k  (k>m)
      phi(n/k)                      。。。。。。。。。。。。。
           ：                k1 k2    n           2     n/k1 n/k2  
        k1,k2                ？                    
*/
#include<stdio.h>
#include<math.h>
int num[40000],cnt2;
int phi(int x)//       
{  
    int i, res=x;  
    for (i = 2; i <(int)sqrt(x * 1.0) + 1; i++)  
        if(x%i==0)  
        {  
            res = res /i * (i - 1);  
            while (x % i == 0) x /= i; //   i        
        }  
        if (x > 1) res = res /x * (x - 1);//          
        return res;  
}  
int main()
{
    int i,Cas;
    scanf("%d",&Cas);
    while(Cas--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        cnt2=0; int s=0;
        for(i=1;i*i<n;++i)//  n       
            if(n%i==0)
            {
			//	if(i>=m)
              //   s+=phi(i);
			//	if(n/i>=m)
			//	 s+=phi(n/i);
				if(i>=m)
                num[cnt2++]=i;
				if(n/i>=m)
                   num[cnt2++]=n/i;
            }
	    if(i*i==n&&n%i==0&&i>=m) num[cnt2++]=i; 
        for(i=0;i<cnt2;++i)
               s+=phi(n/num[i]);
        printf("%d
",s);
    }
    return 0;
}