Hike News
Hike News

互质环与最小公倍数的几种求法

算法 本文总阅读量次

互质环(序列)与最小公倍数的几种求法

题目一：互质环

现在我们要把1…n这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多，请输出最大对数.

输入描述:
1
一行一个整数n(1≤ n≤ 1000)。
输出描述:
1
一行一个整数表示答案。
输入：
1
4
输出：
1
4	例：3 2 1 4

很显然，又是个把做题的的同学(小白)弄得晕头的题，实质上她还是个数学题，就看你数学学的好不好了，呵呵！既然相邻的两个数要互质(除了公因子1外没有其他公因数)，那从小到大顺序排序怎么样！好，试一下：1 2 3 4，也是两两互质，对数为4。是不是巧合呢？大家都知道相邻两数(整数)互质，那么怎么说明是确实是一定互质呢?

证明：

转化一下，相邻两数：n-1, n(n>1)，我们用反证法证明一下。

1
2
3
预设结论：这两数不互质，即有除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. 辗转相除法 :

    1.a%b得余数c

    2.如果c = 0,则b为最大公约数

    3.如果c不等于0,则a = b,b = c继续执行步骤1。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #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
2
3
4
1.若a>b，则a=a-b
2.若a < b，则b=b-a
3. 若a=b，则a（或b）即为两数的最大公约数
4. 若a≠b，则再回去执行1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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\n", a); //最大公约数
   printf("The least common multiple:%d\n", m*n/a);	//最小公倍数
}

T(n)与第一种相比，当两个数比较大时，而且仅相差较小的数，循环需要a=b相等才结束，所以T(n)这时会比较大。

3.枚举法：

已知1是一个公约数，但是1不是最大公约数，所以可以检测K=2,3,4…..是否为x和y的公约数，直到k大于x或者y，将公约数存储在gcd的变量中,gcd初值设为1

1
2
3
4
5
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！