题目一：互质环
现在我们要把1…n这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多，请输出最大对数.
输入描述:
一行一个整数n(1≤ n≤ 1000)。
输出描述:
一行一个整数表示答案。
输入：
4
输出：
4 例：3 2 1 4
很显然，又是个把做题的的同学(小白)弄得晕头的题，实质上她还是个数学题，就看你数学学的好不好了，呵呵！既然相邻的两个数要互质(除了公因子1外没有其他公因数)，那从小到大顺序排序怎么样！好，试一下：1 2 3 4，也是两两互质，对数为4。是不是巧合呢？大家都知道相邻两数(整数)互质，那么怎么说明是确实是一定互质呢?
证明：
转化一下，相邻两数：n-1, n(n>1)，我们用反证法证明一下。
预设结论：这两数不互质，即有除1以外的公因数k，n-1=x·k，n=y·k；
那么有n-(n-1)=(y-x)k=1，k=1/(y-x)；
y,x,k都是整数，k>1,则1>y-x，不符合！所以相邻两数互质！证明就完了。
所以结论就是输入几个数就输出几个数，就能构造互质环(互质对数最多的，两两互质)。
题目二：最小公倍数
有人说求最小公倍数不很简单吗？我想说的是，你是用那种方法求得，而且算法复杂度小，效率高吗？现在我们就现场讨论一波！
最小公倍数=两整数的乘积÷最大公约数 。 所以该问题可以转化为求最大公约数。而最大公约数有这几种求法：
-
辗转相除法 :
1.a%b得余数c
2.如果c = 0,则b为最大公约数
3.如果c不等于0,则a = b,b = c继续执行步骤1。
#include<iostream>
using namespace std;
long long lcm(long long x, long long y){
long long maxs = max(x,y);
long long mins = min(x,y);
long long t = maxs % mins;
while(t != 0){
maxs = mins;
mins = t;
t = maxs % mins;
}
return x * y/mins;
}
int main(){
long long x, y; //x,y很大
cin >> x >> y;
cout<<lcm(x,y)<<endl;
return 0;
}最优算法，t最快接近最大公约数，因为是进行求模运算，所以比相减来得更快。T(n)应该是接近常数级，S(n)的话，由于lcm函数中进行了maxs,mins赋值，空间复杂度降低，和相减法差不多。
2 .相减法:
两数之差与最大公约数成倍数关系。
1.若a>b，则a=a-b
2.若a < b，则b=b-a
3. 若a=b，则a（或b）即为两数的最大公约数
4. 若a≠b，则再回去执行1
#include<stdio.h>
int main ( ) /* 相减法求最大公约数 */
{
int m, n, a, b, c;
scanf ("%d,%d", &a, &b);
m=a; n=b;
/* a, b不相等，大数减小数，直到相等为止。*/
while ( a!=b) {
if (a>b) a=a-b;
else b=b-a;
}
printf("The largest common divisor:%d
", a); //最大公约数
printf("The least common multiple:%d
", m*n/a); //最小公倍数
}
T(n)与第一种相比，当两个数比较大时，而且仅相差较小的数，循环需要a=b相等才结束，所以T(n)这时会比较大。
3.枚举法：
已知1是一个公约数，但是1不是最大公约数，所以可以检测K=2,3,4…..是否为x和y的公约数，直到k大于x或者y，将公约数存储在gcd的变量中,gcd初值设为1
int gcd = 1;
for(int k = 2;k <= x&&k <= y;k++){
if(x % k == 0&& y % k == 0)
gcd = k;
}
当问题规模很大时，这个算法最不好，还是从小到大枚举，T(n)就很大了，k需要不断被自加1赋值，还要判断取模等等，循环次数过多。
今天的算法分享就完了，任务结束，别忘了点赞！hh！
公众号：小码之光(文章首发)
GitHub: github.com/coderxm/