本文主要是介绍gcd简单应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 相等的最小公倍数 | ||||||
| ||||||
| 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简单应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
