精华内容
下载资源
问答
  • 欧几里得

    2020-08-04 20:28:45
    欧几里得扩张模板 /** * 扩展欧几里得算法模板 * x=k1 * y=x1-a/b*k1 */ public class f扩展欧几里得 { static long x;//储存ax static long y;//储存by public static void main(String[] args) { try {/...

    欧几里得扩张模板

    /**
     * 扩展欧几里得算法模板
     * x=k1
     * y=x1-a/b*k1
     */
    public class f扩展欧几里得 {
    	  static long x;//储存ax
    	  static long y;//储存by
    public static void main(String[] args) {     
    	try {//2x+7y=1
    		long f=linearEquation(3,9,6);
    		System.out.println(f);//最大公约数
    		System.out.println(x+" "+y);
    	} catch (Exception e) {
    		// TODO Auto-generated catch block
    		e.printStackTrace();
    	}
    }
    private static long ext_gcd(long a, long b) {
    	// TODO Auto-generated method stub
    	if(b==0) {//初始化
    		x=1;
    		y=0;
    		return a;
    	}
    	long  res=ext_gcd(b,a%b);//最大公约数     res=a
    	long x1=x;//备份 上一个的      
    	x=y;//更新x //  0=x==y=0       1到了 1x+0b=1底层 然后层层返回   a  0  =1	        
    	y=x1-a/b*y;//更新y  0=y==1-上次的a/b*0;
    	return res;//返回最大公约数,和x,y
    }
    /**
     * 线性方程
     * ax+by=m 当m时gcd(a,b)倍数时有解
     * 等价于ax = m mod b*/
    public static long linearEquation(long a,long b,long m)throws Exception {
    	long d=ext_gcd(a, b);//返回一个公约数
    	if(m%d!=0) {
    		 throw new Exception("无解");//抛异常
    	}
    	long n=m/d;//约一下,考虑m是d的倍数
    	x*=n;
    	y*=n;
    	return d;//返回最大公约数
    }
    }
    
    
    展开全文
  • 欧几里得 扩展欧几里得模板

    1.GCD

    int gcd(int a, int b)
    {
        if(!b) return a;
        return gcd(b,a%b);
    }

    2.扩展欧几里得

    • 求a和b的最大公约数,
    • 求整数x和y,使得ax+by=gcd(a,b)
    void  exgcd(int a, int b, int& d, int& x, int& y)
    {
        if(!b){ d = a; x = 1; y = 0;}
        else{ exgcd(b, a%b, d, y, x); y -= a/b*x; }
    }

    得到x和y后,可继续得到ax+by=c的整数解,下面计算了x

    bool solve(int a, int b,int c, int& x,int& y)
    {
        int d;
        exgcd(a, b, d, x, y);
        if(!d || c%d) return false;
        x *= c/d;
        y *= c/d;
        a /= d;
        b /= d;
        if(a<0) a=-a;
        if(b<0) b=-b;
        ((x %= b) += b) %= b;//此时x+mb,y-ma都是解,m为自然数  
        return true;
    }
    展开全文
  • 欧几里得 & 扩展欧几里得
     欧几里得 扩展欧几里得

    时间复杂度T(n)O(log2n);

    空间复杂度S(n)O(n);

     

    Advantages

    1、    时间复杂度不高,和普通欧几里得一样;

    2、    代码简洁,易于编写;

    3、    适用于数学问题求解;

    Disadvantages

    1、    代码难以理解,需要学会数学公式的推理;

    2、    用途不广,适用范围较小;

     

    注意:

    1、    适用于ax + by = gcd(a, b)的方程求解;

    2、    一般化为ax + by = 1,也就是将ab除以最小公约数;

    3、    计算过程中,若要交换两数,则最后需进行判断哪个是答案;

    4、    若求取得是ax + by = gcd(a, b) *k, 最后的答案也要乘k

     

    算法实现:

    1)    普通欧几里得

    gcd(a, b) = gcd(b, a % b), 不断迭代,直到b = 0a就是最大公约数

    2)    拓展欧几里得

    ax + bx = gcd(a, b) = gcd(b, a % b), 不断迭代,直到b = 0x = 1, y = 0;

     

    普通欧几里得:

    适用题型:

    求两个数a,b的最大公约数gcd(a,b)

    输入:ab两个整数

    输出:ab的最大公约数

     

    Source

    long long gcd(long long a, long long b) {
    	return b ? gcd(b, a % b) : a;
    } 

    拓展欧几里得:

    适用题型:

    青蛙的约会【扩展欧几里得,浙江省选2002

    题目背景

    POJ1061

    ZJOI2002

    TJOI2002

     

    题目描述

    两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。

     

    我们把这两只青蛙分别叫做青蛙 A 和青蛙 B,并且规定纬度线上东经 0 度处为原点,由东往西为正方向,单位长度 1 米,这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x,青蛙 B 的出发点坐标是 y。青蛙 A 一次能跳 m 米,青蛙 B 一次能跳 n 米,两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。

     

    输入格式

    输入有多组数据,每组输入数据只包括一行 5 个整数 xymnL

    其中 x≠y2,000,000,0000m,n2,000,000,0000L2,100,000,000 

     

    输出格式

    对每组数据,输出一行,为一个整数,即碰面所需要的跳跃次数,如果永远不可能碰面则输出一行“Impossible” 

    样例数据 1

    输入 

    1 2 3 4 5

    输出

    4

    Source:

    /*
    	created by scarlyw
    */
    #include <cstdio>
    #include <string>
    #include <algorithm>
    #include <cmath>
    #include <iostream>
    #include <cstring>
    #include <cctype>
    
    inline char read() {
    	static const int IN_LEN = 1024 * 1024;
    	static char buf[IN_LEN], *s, *t;
    	if (s == t) {
    		t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
    		if (s == t) return -1;
    	}
    	return *s++;
    }
    
    template<class T>
    inline void R(T &x) {
    	static char c;
    	static bool iosig;
    	for (c = read(), iosig = false; !isdigit(c); c = read()) {
    		if (c == -1) return;
    		if (c == '-') iosig = true;
    	}
    	for (x = 0; isdigit(c); c = read())
    		x = ((x << 2) + x << 1) + (c ^ '0');
    	if (iosig) x = -x;
    }
    
    const int OUT_LEN = 1024 * 1024;
    char obuf[OUT_LEN], *oh = obuf;
    inline void write_char(char c) {
    	if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
    	*oh++ = c;
    }
    
    template<class T>
    inline void W(T x) {
    	static int buf[30], cnt;
    	if (x == 0) write_char('0');
    	else { 
    		if (x < 0) write_char('-'), x = -x;
    		for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
    		while (cnt) write_char(buf[cnt--]);
    	}
    }
    
    inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
    
    long long x, y, m, n, l, t, a, b, c;
    
    long long gcd(long long a, long long b) {
    	return b ? gcd(b, a % b) : a;
    } 
    
    inline void ext_gcd(long long a, long long b, long long &x, long long &y) {
    	b ? (ext_gcd(b, a % b, y, x), y -= a / b * x) : (x = 1, y = 0); 
    }
    
    int main() {
    	R(x), R(y), R(m), R(n), R(l);
    	a = m - n, b = l, c = y - x, t = gcd(a, b);
    	if (c % t) std::cout << "Impossible", exit(0);
    	a /= t, b /= t, c /= t, ext_gcd(a, b, x, y); 
    	if (b < 0) b = -b;
    	x *= c, std::cout << (x % b + b) % b;
    	return 0;
    }
    


    算法分析:

    此题其实就是扩展欧几里德算法——求解不定方程,线性同余方程。

    设跳跃s步后两青蛙相遇, (x+ m * s)为原坐标为x的青蛙在相遇处的坐标值;(y +n * s) 为原坐标为y的青蛙在相遇处的坐标值。两个青蛙如果在第一圈相遇,相遇处坐标相同,则坐标差为0;如果在第二圈相遇,则相遇坐标差为2 * L……,所以相遇处坐标差为k * L(k= 0, 1, 2....)
    则必满足以下等式:
    (x + m * s) - (y + n * s) = k * L (k = 0, 1, 2....)
    稍微变一下形得:
    (n - m) * s + k * L = x - y
    a = n- m, b = L, c = x - y, 
    a * s + b * k = c 
    只要上式存在关于sk的整数解,则两青蛙能相遇,否则不能。所以,c一定是gcd(a ,b)的倍数;看到这里就很容易想到扩展欧几里得。

    算法实现:

    1)    推出公式:(n - m) * s + k * L =x - y

    2)    将公式简化为a * s + b * k = c; 求出gcd(a, b) = t,若c % t == 0则可进行下一步计算,否则不可能实现。

    3)    a, b, c分别除以t,得到a0 * s + b0 * k = c0;(a0 = a / t; b0 = b / t; c0 = c / t)因为此时的a0, b0最大公约数一定为1;所以可以求出a0 *s0 + b0 * k0 = 1的整数解s0, y0s = s0* c0 = s0 * c / t; k = k0 * c0 = k0 * c / t; 从而求出需要的解s

    4)    因为最后的s一定是大于0且小于l的值,所以最后通过 (s % l + l)% l 保证取值范围;

     

    展开全文
  • 欧几里得空间

    2018-10-15 18:28:20
    实数域内,定义了内积的线性空间就是欧几里得空间。介绍了欧几里得空间中的正交基及如何将普通基化成正交基的施密特正交化方法,并介绍了正交变换的概念及其性质
  • 扩展欧几里得

    2021-01-20 13:22:23
    朴素欧几里得: gcd(a,b)=gcd(b,a mod b) 。 这个是比较好证明的: 假设 a=k∗b+r ,有 r=a mod b 。不妨设 d 为 a 和 b 的一个任意一个公约数,则有 a≡b≡0(mod d) 。 由于同余的性质 a−kb ≡ r ≡ 0(mod d) 因此...
  • 欧几里得/扩展欧几里得欧几里得算法简介扩展欧几里得算法简介 欧几里得算法 简介 欧几里得算法,也叫辗转相除,简称 gcdgcdgcd,用于计算两个整数的最大公约数. 定义 gcd(a,b)gcd(a,b)gcd(a,b) 为整数 aaa 与 bbb 的...

    欧几里得算法

    简介

    欧几里得算法,也叫辗转相除,简称 gcdgcd,用于计算两个整数的最大公约数.
    定义 gcd(a,b)gcd(a,b) 为整数 aabb 的最大公约数.

    引理:gcd(a,b)=gcd(b,amod&ThinSpace;&ThinSpace;b)gcd(a,b)=gcd(b,a\mod b)

    1.设 aabb 的最大公约数为 gg,则 a=m1×ga=m_1\times g , b=m2×gb=m_2\times g 易知 m1m_1m2m_2 互质。
    2.设 q=abq=\lfloor\dfrac{a}{b}\rfloor , r=amod&ThinSpace;&ThinSpace;b=ap×b=(m1p×m2)×gr=a\mod b=a-p\times b=(m_1-p\times m_2)\times g,由1得 bbrr 的最大公约数为 gg ,且 m2m_2(m1p×m2)(m_1-p\times m_2) 互质。

    证明m2m_2(m1p×m2)(m_1-p\times m_2) 互质:

    假设 m2m_2(m1p×m2)(m_1-p\times m_2) 的最大公约数为 kk,且k2k \ge 2(两数不互质)。
    &ThickSpace;&ThickSpace;m2=n1×k\implies m_2=n_1\times km1p×m2=n2×km_1-p\times m_2=n_2\times k
    ap×b=r&ThickSpace;&ThickSpace;a=p×b+r&ThickSpace;&ThickSpace;a-p\times b=r\iff a=p\times b + r\iff
    a=n2×k×g+p×n1×k×g&ThickSpace;&ThickSpace;a = n_2\times k\times g + p\times n_1\times k\times g\iff
    a=(n2+p×n1)×kga=(n_2+p\times n_1)\times kg,又 b=n1×kgb=n_1\times k g
    aabb 的最大公约数为 kgkg ,跟已知矛盾,即 m2m_2(m1p×m2)(m_1-p\times m_2) 互质.

    b=0b=0gcd(a,b)=agcd(a, b)=a

    int gcd(int a. int b) //a,b大小不影响
    {
    	return b ? gcd(b. a%b) : a;
    }
    

    扩展欧几里得算法

    简介

    扩展欧几里德算法,简称 exgcdexgcd 是用来在已知a, b求解一组x,y,使它们满足贝祖等式/裴蜀定理不了解可以戳一下(σ゚∀゚)σ…:*☆):
    ax+by=gcd(a,b)=dax+by = gcd(a, b) =d
    让我们简单的推导一下过程
    ax+by=gcd(a,b)=gcd(b,a%b)=bx+(a%b)yax+by=gcd(a,b)=gcd(b,a\%b)=bx&#x27;+(a\%b)y&#x27;

    然后我们就可以开始了

    &ThickSpace;&ThickSpace;ax+by=bx+ay(a/b)by=ay+b(x(a/b)y)\implies ax+by=bx&#x27;+ay&#x27;-(a/b)by&#x27;=ay&#x27;+b(x&#x27;-(a/b)y&#x27;)

    于是得到一组解 x=y,y=x(a/b)yx=y&#x27;,y=x&#x27;-(a/b)y&#x27;
    接着考虑边界条件 (b=0)(b=0)ax=gcd(a,0)ax=gcd(a, 0) 显然成立.
    当然,不定方程会有很多很多解,这时,我们设最小正整数解为 x0,y0x_0, y_0,则通解为 x=x0+bgcd(a,b),y=y0+agcd(a,b)x=x_0+\dfrac{b}{gcd(a, b)}, y=y_0+\dfrac{a}{gcd(a, b)}

    至于证明,它死了,将通解带入方程式即可.

    应用

    hdu2669(模板题)

    题目描述
    给定两个数 a,ba, b ,求满足 ax+by=1ax+by=1x,yx,yxx 为满足条件的最小正整数.

    题解
    用扩展欧几里得,迭代求出最小的 xx 即可.

    代码

    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    void exgcd(LL a, LL b, LL &x, LL &y)
    {
            if (!b)
            {
                    x = 1, y = 0;
                    return ;
            }
            exgcd(b, a%b, y, x);
            y -= x * (a/b);
    }
    
    LL gcd(LL a, LL b)
    {
            return b ? gcd(b, a%b) : a;
    }
    
    int main()
    {
            LL a, b, x, y;
            while (scanf("%lld%lld", &a, &b) == 2)
            {
                    if (gcd(a, b) != 1)
                    {
                            puts("sorry");
                            continue;
                    }
                    exgcd(a, b, x, y);
                    while (x < 0)
                    {
                            x += b;
                            y -= a;
                    }
                   // x = (x % b + b) % b;
                    printf("%lld %lld\n", x, y);
            }
    
            return 0;
    }
    

    洛谷P1082(同余方程)

    题目描述
    求关于 xx 的同余方程ax1(modb)a x \equiv 1 \pmod {b} 的最小正整数解。

    题解
    ax1(modb)&ThickSpace;&ThickSpace;ax+by=1a x \equiv 1 \pmod {b}\implies ax+by=1

    代码

    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    void exgcd(LL a, LL b, LL &x, LL &y)
    {
            if (!b)
            {
                    x = 1, y = 0;
                    return ;
            }
            exgcd(b, a%b, y, x);
            y -= x * (a/b);
    }
    
    int main()
    {
            LL a, b, x, y;
            scanf("%lld%lld", &a, &b);
            exgcd(a, b, x, y);
            while (x < 0)
                    x += b;
            printf("%lld\n", x);
    
            return 0;
    }
    

    hdu1356(解不定方程)

    题目描述

    展开全文
  • 扩展欧几里得算法详解

    万次阅读 多人点赞 2018-08-17 00:38:27
    为了介绍扩展欧几里得,我们先介绍一下贝祖定理: 即如果a、b是整数,那么一定存在整数x、y使得ax+by=gcd(a,b)。 换句话说,如果ax+by=m有解,那么m一定是gcd(a,b)的若干倍。(可以来判断一个这样的式子有没有解...
  • 欧几里得算法和扩展欧几里得算法

    千次阅读 2020-03-09 23:29:46
    文章目录摘要欧几里得算法扩展欧几里得算法最小正整数解 摘要 本文主要讲解欧几里得算法和扩展欧几里得算法。 欧几里得算法 欧几里得算法就是辗转相除法,用于求两个数的最大公约数。 设gcd(a,b)gcd(a, b)gcd(a,b) ...
  • 欧几里得算法 欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数(gcd)。 其计算原理依赖于下面的定理: 定理:gcd(a,b) = gcd(b,a mod b) (a&gt;b 且a mod b 不为0) 证明:a可以表示成a = kb...
  • 欧几里得我们先来看下求整数a,b的最小公约数gcd(a,b)的算法。即欧几里得算 法。 首先要知道gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|) 我们不妨考虑a,b为正整数的情况。令gcd(a,b)=g,则 a=k1gb=k2ga=k_1g\\ b=...
  • 欧几里得和拓展欧几里得算法 1.欧几里得算法 ⑴算法内容 欧几里得算法又称辗转相除法,用于计算两个整数的最大公约数。 gcd(a,b)=gcd(b,a(modb)) gcd(a, b) = gcd(b, a (mod b)) gcd(a,b)=gcd(b,a(modb)) ⑵下面给...
  • 1.欧几里得 求最大公约数,最小公倍数 (1)递归的写法:int gcd(int a,int b) {return b?gcd(b,a%b):a;} (2)辗转相除法: int gcd(int a,int b) { if(a<b) return gcd(b,a); int r; while(b) {r=a%b;a=b;b=r;} return...
  • 欧几里得 int gcd(int a,int b){ return (b==0)?a:gcd(b,a%b); //一条语句搞定(三元运算符)装逼,跟上面略有不同,上面做到t=0,这里做到b=0 } 拓展欧几里得 int gcd(int a,int b){ return (b==0)?a:...
  • 欧几里得算法:求最大公约数 //递归形式 int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }   //非递归形式 int gcd(int a,int b) { while(b&gt;0){ int c=a%b; a=b; b=c; } return a;...
  • 欧几里得算法/扩展欧几里得算法

    万次阅读 多人点赞 2017-07-17 12:07:43
    ... 欧几里得(希腊文:Ευκλειδης ,公元前330年—公元前275年),古希腊数学家。他活跃于托勒密一世(公元前364年-公元前283年)时期的亚历山大里亚,被称为“几何之父”,他最著...
  • 欧几里得相移算法

    2019-01-24 10:25:18
    matlab欧几里得矩阵算法,phase shift extraction algorithm based on euclidean matrix norm
  • 欧几里得算法的应用 欧几里得算法的应用 欧几里得算法的应用
  • 欧几里得算法

    2020-12-17 18:33:23
    2,欧几里得算法的理论基础——带余除法定理 3,欧几里得算法的泛化 (1)多项式 (2)复数 4,拓展欧几里得算法 5,实战 (1)更相减损术 UVALive - 7045 Last Defence (2)欧几里得算法——最大公约数 ...
  • 欧几里得距离

    千次阅读 2019-02-10 08:55:45
    欧几里得距离,又称欧氏距离,是最常见的距离度量,衡量的是多维空间中各个点之间的绝对距离。在计算相似度(比如人脸识别)的场景下,欧几里得距离是比较直观、比较常见的一种相似度算法。欧氏距离越小,相...
  • 1欧几里得算法 欧几里得算法(辗转相除法)是解决两个数,a,b的最大共因数的(最大公约数) 中国古代有个 更相减损术(高中课本学过)与此同理   先不管他们那不明觉厉的名字。。。。。看一下思想   假设a,...
  • 用PHP实现欧几里得和拓展欧几里得计算的程序。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,686
精华内容 15,874
关键字:

欧几里得