GCD
时间限制(普通/Java) : 2000 MS/ 6000 MS 运行内存限制 : 65536 KByte总提交 : 142 测试通过 : 24
比赛描述
The greatest common divisor GCD(a,b) of two positive integer a and b,sometimes written (a,b),is the largest divisior 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 difficlut problem.
Given integer N and M,how many integer X satisfies 1<=X<=N and (X,N)≥M.
输入
The first line or input is an integer T(<=3000)representing the number of test cases.The following T lines each contains two numbers N and M(1<=N<=1000000000,0<=M<=1000000000),representing a test case.
输出
For each test case,output the answer on a single line.
样例输入
3
1 1
10 2
10000 72
样例输出
1
6
260
题目来源
第九届中山大学程序设计竞赛预选题
题意：给定n和m，求出在1到n的范围内的数x，满足GCD(x,n)>=m的x的个数。
分析：题目类似于欧拉函数问题。欧拉函数问题：给定一个整数n，求出小于它的数中和它互质的数的个数。这一题可以转化一下，题意中要求GCD(x,n)>=m，那么如果一个数x，x=a*b，a是大于等于m的一个属于n的因子，且b是一个质数，x即可满足条件。题目中要求求出的数全部满足这样的条件，且不满足这个条件的数绝对不是所求的数。现在题目转化为欧拉函数，求取euler(n/a)得到的质数的个数即时该因子下满足条件的数的个数。遍历一遍因子，累加即可。需要注意的是如果存在平方数的话，需要判断，防止重复累加。见AC代码：
#include<stdio.h>刷题长见识……欧拉函数模板题：POJ 2407
#include<math.h>
int euler(int x)//1到x之间和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 T;
scanf("%d",&T);
while(T--)
{
int n,m,res=0;
scanf("%d%d",&n,&m);
for(int i=1; i*i<=n; i++)
{
if(n%i==0)
{
if(n/i>=m)//要求的最大公约数需要大于m
res+=euler(i);
if(i>=m&&i*i!=n)//防止平方数 重复加
res+=euler(n/i);
}
}
printf("%d\n",res);
}
}
特记下，以备后日回顾。