gcd简单应用

本文主要是介绍gcd简单应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

相等的最小公倍数

Time Limit: 1000 MS Memory Limit: 65536 K Total Submit: 145(55 users) Total Accepted: 63(44 users) Rating:  Special Judge: No

Description

定义An为1，2，…，n的最小公倍数，例如，A1 = 1，A2 = 2，A3 = 6，A4 = 12，A5 = 60，A6 = 60。 请你判断对于给出的任意整数n，An是否等于An – 1。

Input

本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。 对于每组测试数据： 第1行 包含一个整数n (2 ≤ n ≤ 106)。

Output

对于每组测试数据： 第1行 如果An等于An-1则输出YES否则输出NO。

Sample Input

1 6

Sample Output

YES

Source

哈理工2012春季校赛热身赛 2012.04.03

Author

齐达拉图@HRBUST

首先判断该数n是否为素数，，是素数的话，，An  An-1不可能相等，，因为An会比An-1 乘上一个更大的新素数。。

然后在n不是素数的前提下，，判断n是否存在 一对互素的因子..即n=a*b（a，b互素）（即gcd(a,b)==1）.存在则输出YES 

/**怎么判断相邻两个数的lcm是否相等.**/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int gcd(int a,int b)
{if(b==0) return a;else    return gcd(b,a%b);
}
int main()
{int T,n;scanf("%d",&T);while(T--){int i;bool p=true;scanf("%d",&n);int temp=(int)sqrt((double)n);if(n==2){printf("NO\n");continue;}for(i=2;i<=temp;i++)if(n%i==0) break;if(i==temp+1){printf("NO\n");continue;}for(i=2;i<=temp;i++){if(n%i==0){int q=n/i;if(gcd(q,i)==1){p=false;break;}}}if(p) printf("NO\n");else printf("YES\n");}return 0;
}

这篇关于gcd简单应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---