GCD |
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 76 Accepted Submission(s): 50 |
|
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 |
|
Sample Output
1 |
|
Source
ECJTU 2009 Spring Contest
|
|
Recommend
lcy
|
/*
题意：给出N，M让你求出 X的个数 ，X满足GCD(X,N)>=M; 初步思路：首先N的比M大的因子肯定是，是这个因子的倍数的也是。除此之外就没了，因为其他的数GCD(other,N)=1,如果M等于1的话，直接输出N就行了
现在的问题就是怎么找因子的倍数，因为会有重复的，res=N/x(x是N的因子);对于因子x有res个可满足的结果，但是在计算过程中会有重复的存在，
这样，令pi<=res && GCD(pi,res)==1,这样保证了 pi*x不会重复，就转化成了，求N/x的欧拉函数 */
#include<bits/stdc++.h>
using namespace std;
/**************************欧拉函数模板*****************************/
//直接求解欧拉函数
int euler(int n){ //返回euler(n)
int res=n,a=n;
for(int i=;i*i<=a;i++){
if(a%i==){
res=res/i*(i-);//先进行除法是为了防止中间数据的溢出
while(a%i==) a/=i;
}
}
if(a>) res=res/a*(a-);
return res;
}
/**************************欧拉函数模板*****************************/
int solve(int n,int m){
if(m==) return n;
int cur=;
for(int i=;i*i<=n;i++){
if(n%i==){//i是n的因子
if(i>=m){
cur+=euler(n/i);
}
if(i*i!=n){//对面的因子
if(n/i>=m){
cur+=euler(n/(n/i));
}
}
}
}
return cur+;
}
int t;
int n,m; int main(){
//freopen("in.txt","r",stdin);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
printf("%d\n",solve(n,m));
}
return ;
}