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

    2020-10-04 22:33:55
    关于欧几里得算法和拓展欧几里得算法 求解两个数的最大公约数,有三种比较常用的算法:蛮力法、更相减损法以及欧几里得算法。在这里我们只讨论欧几里得算法,蛮力法的时间复杂度过大,不适合求解数据量比较大情况。...

    关于欧几里得算法和拓展欧几里得算法
    求解两个数的最大公约数,有三种比较常用的算法:蛮力法、更相减损法以及欧几里得算法。在这里我们只讨论欧几里得算法,蛮力法的时间复杂度过大,不适合求解数据量比较大情况。而更相减损法与欧几里得算法其实有共通性。
    首先,欧几里得算法,可以用一个函数gcd()表示,我们假设现在有两个数a和b。
    1、gcd(a,b)= gcd(b,a)
    2、gcd(a,b)=gcd(b,a%b)
    3、gcd(a,0)=a
    通过以上三个公式,我们就可以求解两个数的最大公约数了。
    这里给一个例子:假设我们要求104,195的最大公约数
    gcd(104,195)=gcd(195,104)=gcd(104,91)=gcd(91,13)=gcd(13,0)=13
    根据上面的例子,可以看出欧几里得算法比蛮力法快。

    int gcd(int a,int b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    

    另外,拓展欧几里得算法不仅可以计算出两个数的最大公约数,还能给出
    ax+by=gcd(a,b)的一个x,y的解(x,y不止一组解)
    我们已经知道了欧几里得算法的一些公式,通过这些公式我们便可以很方便的推导出拓展欧几里得算法。
    1、ax+by=gcd(a,b)=gcd(b,a%b)
    2、 gcd(b,a%b)=bx+(a%b)y
    3、gcd(a,0)=ax+0y=a 得x=1,y=0
    (注:以上三个式子中,x,y相互无关)
    通过上面的式子,我们可以知道
    前一组x,y的解与后一组x,y的解有关。
    我们设 ax+by=gcd(a,b)、gcd(b,a%b)=bx’+(a%b)y’

    已知a%b=a-[a/b]*b([a/b]表示a/b后截掉小数部分)
    gcd(b,a%b)=bx’+(a-[a/b]*b)y’=ay’+b(x’-[a/b]*y’)
    再根据我们设的式子,不难看出
    ax+by= ay’+b(x’-[a/b]*y’)
    所以,后一个的解可以推出前一个的解,可得
    x=y’
    y=x’-[a/b]*y’
    这样,我们可以很方便得写出递归版本的程序

    int exgcd(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        else
        {
            int d,t;
            d=exgcd(b,a%b,x,y);
            t=x;
            x=y;
            y=t-(a/b)*y;//以上可写成d=exgcd(b,a%b,y,x);y=y-(a/b)*x;
            return d;
        }
    }
    
    展开全文
  • 拓展欧几里得算法

    2017-10-26 00:33:28
    拓展欧几里得算法
    首先你要知道欧几里得算法(就是辗转相除法)

    Gcd(a,b)=gcd(b,a%b)


    int gcd(int a,int b)

    {

        return b?gcd(b,a%b):a;

    }


    那么来看拓展欧几里得算法

    先上代码

    Gcd(a,b)=ax+by   这是一个不定方程,扩欧用来求x,y的整数解

    void exgcd(int a,int b,LL &x,LL &y){  
        if(b==0){x=1,y=0;return;}  
        exgcd(b,a%b,x,y);  
        LL t=x;  x=y,y=t-a/b*y;  
    }  


    那么为什么会这样呢

    让我们来证明一下:

    我们想求一组(x,y)使得gcd(a,b)=ax+by

    根据b≠0 -->gcd(a,b)=gcd(b,a%b)

    如果我们现在有x’,y’,那么gcd(b,a%b)=b*x'+(a%b)*y'

    那么我们现在可以令 ax+by=b*x'+(a%b)*y'       ①式

    注意到a%b=a-a/b*b

    带入①式得:ax+by=b*x'+(a-a/b*b)*y'             ②式

    注意它的每一项仅仅是由a,b相关的

    改造

    右边也以a,b为元 ax+by=a*y'+b*(x'-a/b*y')

    得出一组特解:x=y'  y=x'-a/b*y'

    它这个递归的基为b=0

    当b=0时,ax+by=gcd(a,b) 可以得出x=1,y=0;

    证毕。。


    证明结束了

    如果还想看看题目的话可以看看noip 2012 D2T1


    展开全文
  • 博主链接 欧几里得 int gcd(int a,int b){ return (b==0)?a:gcd(b,a%b); //一条语句搞定(三元运算符)装逼...拓展欧几里得 int gcd(int a,int b){ return (b==0)?a:gcd(b,a%b); //一条语句搞定(三元运...

    博主链接

    欧几里得

    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:gcd(b,a%b);    //一条语句搞定(三元运算符)装逼,跟上面略有不同,上面做到t=0,这里做到b=0
    
    }
    
    ll lcm(ll a, ll b) {
        return a / gcd(a,b) * b;
    }
    int exgcd(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        int r=exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }

    拓展欧几里得求整数解个数

    ll gcd(ll a, ll b) {
    	return b ? gcd(b, a%b) : a;
    }
    
    ll lcm(ll a, ll b) {
    	return a / gcd(a, b) * b;
    }
    
    ll extend_gcd(ll a, ll b, ll&x, ll&y) {
    	if (!b) {
    		x = 1;
    		y = 0;
    		return a;
    	}
    	ll xt = 0, yt = 0;
    	ll d = extend_gcd(b, a % b, xt, yt);
    	x = yt;
    	y = xt - yt * (a / b);
    	return d;
    }
    
    ll cal(ll a, ll b, ll n) {    //计算ax+by == n的非负整数解组数
    	ll x = 0, y = 0, d;
    	d = extend_gcd(a, b, x, y);
    	if (n % d != 0) {
    		return 0;
    	}
    	x *= n / d, y *= n / d;
    	ll LCM = lcm(a, b);
    	ll t1 = LCM / a, t2 = LCM / b;
    	if (x < 1) {
    		ll num = (1 - x) / t1;
    		x += num * t1;
    		y -= num * t2;
    		if (x < 1) {
    			y -= t2;
    			x += t1;
    		}
    	}
    	if (y < 1) {
    		ll num = (1 - y) / t2;
    		y += num * t2;
    		x -= num * t1;
    		if (y < 1) {
    			y += t2;
    			x -= t1;
    		}
    	}
    	ll ans = x > 0 && y > 0;
    	if (ans) {
    		ans += min((x - 1) / t1, ((n - 1) / b - y) / t2);
    		ans += min((y - 1) / t2, ((n - 1) / a - x) / t1);
    	}
    	return ans;
    }

     

    展开全文

空空如也

空空如也

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

拓展欧几里得