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


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

题目一:互质环

现在我们要把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. 辗转相除法 :

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


今天的算法分享就完了,任务结束,别忘了点赞!hh!


文章作者: coderxm
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 coderxm !
评论
 上一篇
opera、google、firefox浏览器的选择 opera、google、firefox浏览器的选择
作者:coderxm公众号:小码之光 首先介绍:先介绍本人用的最多的浏览器:火狐 Mozilla Firefox,中文俗称“火狐”,是一个自由及开放源代码的浏览器,使用Gecko排版引擎,支持多种操作系统,如Windows、Mac OS及
2020-07-19
下一篇 
年轻母牛的故事 年轻母牛的故事
年轻母牛的故事题目是这样的:有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛? 输入​ 输入数据由多个测试实例组成,每个测试实例占一行,包括一个整数n(0
2020-07-08
  目录