精华内容
下载资源
问答
  • 辗转相减法

    千次阅读 2020-03-24 16:13:47
    证明方法与辗转相除法类似。 2. 应用 辗转相除法可以用来求若干个形如(pq)ri(\frac pq)^{r_i}(qp​)ri​的数的最大公约数,其中: pq\frac pqqp​不可以再表示为次幂的形式 ppp、qqq、rir_iri​均为正整数 ...

    1. 理论依据

    g c d ( a , b ) = g c d ( b , a − b ) gcd(a, b) = gcd(b, a - b) gcd(a,b)=gcd(b,ab)
    证明方法与辗转相除法类似。


    2. 应用

    辗转相除法可以用来求若干个形如 ( p q ) r i (\frac pq)^{r_i} (qp)ri的数的最大公约数,其中:

    • p q \frac pq qp不可以再表示为次幂的形式
    • p p p q q q r i r_i ri均为正整数

    3. 算法推导

    我们要求若干个形如 ( p q ) r i (\frac pq)^{r_i} (qp)ri的数的最大公约数,即求指数的最大公约数,即:
    f ( p x , p y ) = p ( x , y ) = p ( y , x − y ) = f ( p y , p ( x − y ) ) = f ( p y , p x p y ) f(p^x, p^y) = p^{(x, y)}=p^{(y, x-y)}=f(p^y,p^{(x-y)})=f(p^y, \frac {p^x}{p^y}) f(px,py)=p(x,y)=p(y,xy)=f(py,p(xy))=f(py,pypx)

    ps:
    1. 第二个等号由更相减损术得到
    2. x 要大于 y

    代码如下:

    int gcd_sub(int a, int b){
    	if(a < b) swap(a, b);
    	if(b == 1) return a; // 此时p^y = 1即y = 0
    					     // 由于0和任何正整数r的最大公约数都是r,所以此时应返回p^r,即a
    	return gcd_sub(b, a / b);
    }
    

    4. 与辗转相减法的区别

    时间复杂度
    辗转相除法O(logn)
    辗转相减法O(n)

    所以我们在求gcd的时候,通常还是用辗转相除法的。不过在上述这种特殊情况用辗转相除法不太方便的时候,我们采用辗转相减法。

    展开全文
  • 辗转相减法求最大公约数

    千次阅读 2019-05-02 17:27:11
    辗转相减法是一种简便的求出两数最大公约数的方法。(更相减损术) 辗转相减法(求最大公约数),即尼考曼彻斯法,其特色是做一系列减法,从而求得最大公约数。例如 :两个自然数35和14,用大数减去小数,(35,14)->...

    第一次接触这个算法,同时也觉得很奇妙,在本文加以练习,并与大家分享。

    辗转相减法是一种简便的求出两数最大公约数的方法。(更相减损术)

    辗转相减法(求最大公约数),即尼考曼彻斯法,其特色是做一系列减法,从而求得最大公约数。例如 :两个自然数35和14,用大数减去小数,(35,14)->(21,14)->(7,14),此时,7小于14,要做一次交换,把14作为被减数,即(14,7)->(7,7),再做一次相减,结果为0,这样也就求出了最大公约数7。

    个人觉得这个算法确实称得上很神奇,简明实用。

     

    #define _CRT_SECURE_NO_WARNINGS 1
    #include <stdio.h>
    //求两个数的最大公约数,辗转相减法
    int main()
    {
    	int a = 0;
    	int b = 0;
    	printf("please enter:");
    	scanf("%d%d", &a, &b);
    	int ret = 0;
    	while (1)
    	{
    		if (a < b)
    		{
    			int tmp = 0;
    			tmp = a;
    			a = b;
    			b = tmp;
    		}
    		ret = a - b;
    		if (ret == b)//判断
    		{
    			printf("ret = %d", ret);
    			break;
    		}
    		else//交换
    		{
    			a = b;
    			b = ret;
    		}
    	}
    	return 0;
    }

    有段时间没写代码了,这么一小段写的略显尴尬,敲代码还是不能停呀。

    展开全文
  • 程序实现: #include // 辗转相除法 求两个整数值x 和 y 的最大公约数 int gcd(unsigned x, unsigned y) { if (x % y == 0) { printf("%d / %d = %d (余 %d)\n", x, y, x / y ,x % y); return y; } else if ...

    假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法,是这样进行的:
    1997 / 615 = 3 (余 152)
    615 / 152 = 4(余7)
    152 / 7 = 21(余5)
    7 / 5 = 1 (余2)
    5 / 2 = 2 (余1)
    2 / 1 = 2 (余0)
    至此,最大公约数为1
    以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 1997 和 615 的最大公约数 1。

    程序实现:
    #include <stdio.h>
    
    // 辗转相除法 求两个整数值x 和 y 的最大公约数 
    int gcd(unsigned x, unsigned y) {
    
    	if (x % y == 0) {
    		printf("%d / %d = %d (余 %d)\n", x, y, x / y ,x % y);
    		return y;
    	}
    	else if (y % x == 0) {
    		printf("%d / %d = %d (余 %d)\n", y, x, y / x, y % x);
    		return x;
    	}
    	else if (x > y) {
    		printf("%d / %d = %d (余 %d)\n", x, y, x / y ,x % y);
    		return gcd(y, (x % y));
    	}
    	else if (x < y) {
    		printf("%d / %d = %d (余 %d)\n", y, x, y / x, y % x);
    		return gcd(x, (y % x));
    	}
    
    }
    
    int main(void) {
    	unsigned x;
    	unsigned y;
    	puts("请输入x的值:");
    	scanf("%d", &x);
    
    	puts("请输入y的值:");
    	scanf("%d", &y);
    
    	printf("%d 和 %d 的最大公约数为:%d", x, y, gcd(x, y));
    
    	return 0;
    }
    

    运行结果:
    在这里插入图片描述


    辗转相减法:大数减小数,直到两数相等时,即为最大公约数。

    #include <stdio.h>
    
    // 辗转相减法 求两个整数值x 和 y 的最大公约数 
    int gcd(unsigned x, unsigned y) {
    
    	if (x == y) {
    		return x;
    	}
    	else if (x > y) {
    		printf("%d - %d = %d \n", x, y, x - y);
    		return gcd(y, x - y);
    	}
    	else if (x < y) {
    		printf("%d - %d = %d \n", y, x, y - x);
    		return gcd(x, y - x);
    	}
    
    }
    
    int main(void) {
    	unsigned x;
    	unsigned y;
    	puts("请输入x的值:");
    	scanf("%d", &x);
    
    	puts("请输入y的值:");
    	scanf("%d", &y);
    
    	printf("%d 和 %d 的最大公约数为:%d", x, y, gcd(x, y));
    
    	return 0;
    }
    

    运行结果:

    在这里插入图片描述

    展开全文
  • 更相减损法|辗转相减法

    千次阅读 2020-04-27 00:31:31
    时间复杂度 o(n) ...辗转相除法可以用来求若干个形如(p/q)^ri的数的最大公约数,其中: ——p/q不可以再表示为次幂的形式 ​——p、q、ri均为正整数 算法推导 求指数的最大公约数,即: f(p^x...

    时间复杂度

    o(n)

    题目代码

    int gcd(int a,int b)
    {
       if(a==b)return a;
       return a>b?gcd(a-b,b):gcd(b-a,a);
    }
    

    特殊情况

    辗转相除法可以用来求若干个形如(p/q)^ri的数的最大公约数,其中:
    ——p/q不可以再表示为次幂的形式
    ​——p、q、ri均为正整数

    算法推导

    求指数的最大公约数,即:

    f(p^x , p^y)
     = p(x,y)
     = p(y,x-y)
     = f(p^y,p(x-y))
     = f(p^y, p^x / p^y)
    

    X要大于Y

    特殊情况下的代码

    LL gcd_sub(LL a,LL b)
    {
        if(b>a)swap(a,b);
        if(b==1)return a;
        return gcd_sub(b,a/b);
    }
    
    展开全文
  • 求两个数的最大公约数(辗转相减法)

    千次阅读 2019-11-12 17:23:01
    减损法:也叫更减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。 《九章算术》是中国古代的数学专著,其中的“更减损术”可以用来求...
  • 辗转相除法 #include&lt;stdio.h&gt; int main() { int a,b,r,m,n; scanf("%d%d",&amp;a,&amp;b); m=a,n=b; while(b!=0){//被除数不等于0 r=a%b; a=b; b=r;//下一次被除数为r ...
  • 只讲Java 辗转相除法的实现,...//java 辗转相除法求2个数的最大公约数 public class Day002 { static Day002 dy=new Day002(); public static void main(String[] args) { // TODO Auto-generated method st...
  • 根据辗转相减法可得到 gcd(a,b)=gcd(a,∣a−b∣)=gcd(b,∣a−b∣)gcd(a,b)=gcd(a,|a-b|)=gcd(b,|a-b|)gcd(a,b)=gcd(a,∣a−b∣)=gcd(b,∣a−b∣) gcd(a,b,c)=gcd(a,gcd(b,c))=gcd(gcd(a,b),c)gcd(a,b,c)=gcd(a,gcd(b...
  • #include<stdio.h> int f(int x,int y,int z) { int a,b,c,s,d,h; a=x;b=y;c=z; while(x!=y) { if(x>y) x=x-y; else y=y-x; } s=a*b/x; d=s; while(s!=z) { ... else z=z-...
  • 辗转相减法、辗转相除法  --------求两个数的最大公约数 思路1:用辗转相减法 #include int main() { int a = 0; int b = 0; printf("please Enter 2 datas:"); scan
  • 思路:假定98和63的最大公约数是M,那么98=a*M,63=b*M如果要求两个数X,Y的最大公约数T,把X,Y看成由若干个T组成的数,X:TTTTTT...... Y:TTTTTT...... 那么X-Y是什么意思呢?!意思就是X比Y多的T构成的数,这样减的话这...
  • 2.辗转相减法(更相减损法) 3.穷举法 最小公倍数:两数的乘积除以最大公约数 方法: 1.判断大小,并使大数赋给a,小数赋给b; 2.辗转相除法:在两数相除余数不为0的情况下循环相除,直至余数为0并得出最大公约数 3....
  • 这里分别列举辗转相除法,辗转相减法,枚举法三种方法来求最大公约数。 而最小公倍数 = 两个整数的乘积 / 最大公约数。 gcd函数代表求最大公约数,lcm代表求最小公倍数。 1、辗转相除法 ...
  • 很经典的一道题,我们来直接看题目 本题要求两个给定正整数的最大公约数和最小公倍数。...此题的解法有暴力,辗转相除,辗转相减三种 这里为了简洁,我只介绍后两种。 第一种:辗转相减: 首先,上个百...
  • 数论-辗转相减法-第七届蓝桥杯省赛C++A/B组-最大比例 题目: X星球的某个大奖赛设了 M 级奖励。 每个级别的奖金是一个正整数。 并且,相邻的两个级别间的比例是个固定值。 也就是说:所有级别的奖金数构成了一个等比...
  • 辗转相减后得到:GCD(a,b+c,d) 分析就可以得到结论:对于右边的点,若两个点(这里的b和c)连接的点集相同(AB),则这两个点为一类点。 结果答案为所有类点内部权值和的gcd。 而分析哪些点为一类用哈希即可
  • 本文实例讲述了Python基于更减损术实现求解最大公约数的方法。分享给大家供大家参考,具体如下: 先从网上摘录一段算法的描述如下: 更相减损法:也叫 更减损术,是出自《 九章算术》的一种求最大公约数的算法,...
  • 这个题用到了辗转相减法的一个特殊应用 简单分析一下如下 1223. 最大比例 X星球的某个大奖赛设了 M 级奖励。 每个级别的奖金是一个正整数。 并且,相邻的两个级别间的比例是个固定值。 也就是说:所有级别的奖金数...
  • 于是我们可以运用辗转相减法来解决: 设 Q(a,b)Q(a,b)Q(a,b)为 a,ba,ba,b间最大公比例,则 Q(a,b)=Q(qk0,qk1)=qgcd(k0,k1)=qgcd(k1,k1−k0)=Q(qk1,qk1−k0)=Q(b,b/a)Q(a,b)=Q(q^{k_0},q^{k_1})=q^{gcd(k0,k1)}=q^{gcd...
  • 最大公约数 辗转相减法

    千次阅读 2011-01-06 19:33:00
      Code: #include  ...相减法 解最大公约数 int **(int x,int y) {  while(x!=y)  {  if(x>y)  x=x-y;  else  y=y-x;  }  return x; }
  • 最大比例X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。 并且,相邻的两个级别间的比例是个固定值。 也就是说:所有级别的奖金数构成了一个等比数列。比如: 16,24,36,54 其等比值为:3/2 现在,我们...
  • 4.5辗转相减法

    2021-08-04 08:56:01
    #include<stdio.h> int main() { long long int x, y, m, n; scanf("%lld%lld", &x, &y); m = x, n = y; while (x!=y) { if (x>y) x = x-y; else y = y-x; } printf("%lld %lld", x, m*n / x);...}
  • //辗转相减法 O(lgn) int gys ( int m , int n ) { int t ; if ( m < n ) { t = m ; m = n ; n = t ; } if ( m == n ) { return m ; } else { return gys ( m - n , n )...
  • 求公因式-辗转相减法

    2021-11-11 21:33:37
    #include <iostream> using namespace std; int subtraction(int a, int b) { int temp; if (a >= b) { ... //这里是一个关键,相减的过程中会出现小值减大值的情况,必须让其为正值 ... {
  • 辗转相除法 算法描述: 辗转相除法是求两个正整数的最大公约数的一种算法. 有两整数a和b:  ① a%b得余数c  ② 若c=0,则b即为两数的最大公约数  ③ 若c≠0,则a=b,b=c,再回去执行①  例如求27和15的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,556
精华内容 622
关键字:

辗转相减法