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

待我称王封你为后i 2023-02-24 03:58 41阅读 0赞

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

![看戏][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvYnVsbGlu_size_16_color_FFFFFF_t_70_pic_center]

#### 题目一：互质环 ####

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

##### 输入描述: #####

一行一个整数n(1≤ n≤ 1000)。

##### 输出描述: #####

一行一个整数表示答案。

##### 输入： #####

##### 输出： #####

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.辗转相除法 : ####

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\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

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赋值，还要判断取模等等，循环次数过多。  
![strong][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dvYnVsbGlu_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/dc42bfa5f66d472d81490ec33e9ef546.png
[strong]: /images/20230209/157e05282ac94752b89cc334390cc581.png