# 数学训练—-数论HDU 2588 – GCD

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

其中：k>=m

#include <iostream>

using namespace std;
int oula(int n)
{
if(n==1)    return 1;
int m=n;

for(int i=2; i*i<=m; i++)
if(m%i==0)
{
n-=n/i;
while(m%i==0)
m/=i;
}
if(m!=1)
{
n-=n/m;
}
return n;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
int ans=0;
for(int i=1;i<=n;i++)
{
if(n%i) continue;
if(i>=m)
ans+=oula(n/i);
}
cout<<ans<<endl;

}
return 0;
}


for(int i=1;i*i<=n;i++)
{
if(n%i) continue;
if(i>=m&&i*i!=n)
ans+=oula(n/i);
if(n/i>=m)
ans+=oula(i);
}


0