来自  资质荣誉 2019-09-24 00:46 的文章
当前位置: 澳门太阳娱乐手机登录 > 资质荣誉 > 正文

扩展欧几里德算法及其应用

---恢复内容开始---

扩展欧几里德算法

设如下两个方程:

  • ax+by = gcd(a,b) =gcd(b,a % b) = d;

  • bx’+(a%b)y’ = gcd(b,a%b);

那么由辗转相除算法有gcd(a,b) = gcd(b,a %b),
又因 a%b= a - a(a / b) * b;

那么ax+by = bx’+(a%b)y’ = bx’ +(a – [a/b] * b)y’ = ay’ + b(x’ – [a/b]y’),

由恒等关系有: x = y’ , y = (x’ – [a/b]y’),[a/b]表示a/b的值向下取整。

........

那么现在就可以用exgcd(a,b,d,x,y)表示方程ax+by = d,那么由上面一直递归下去,直到 b = 0,递归结束,此时 d = gcd(a,0) =a , x = 1,y =0;【因为 ax+0*y = gcd(a,0)嘛~(这时的意思就是求a和0 两个数的最大公约数,a和0 的最大公约数当然是a)】

比较经典的扩展欧几里德求整数解的问题。

代码实现

int extgcd (int a,int b,int& x,int& y)
{
  int d = a;//为了b == 0 时的特殊情况,gcd(a,0)的最后结果当然是a;返回函数值
  if (b != 0)
  {
    d = extgcd(b,a % b,y,x);
    y -= (a/b) * x;//此处不明白
  }
  else//b == 0 的情况
  {
    x = 1;y = 0;
  }
  return d;
}

对于两个点,如果点为整数点,那么必定能通过扩展欧几里德求出区间中的整点个数,即对方程x+y=x1y2-x2y1 求解。

欧几里德拓展算法的几个应用

由于此题的点精确到小数后1位,我们可以将x1,y1,x2,y2分别放大10倍,问题转变成对方程[10*]*x+[10*]y=100*(x1y2-x2y1)求解。

求解不定方程

例如:求解不定整数方程ax+by = c

求ax+by = c, 令d =gcd(a,b);

那么(a / d ) * x + (b / d )* y = c / d

因为(a / d )、(b / d ) 、x、y都是整数,那么保证原不定整数方程ax+by = c有解的充要条件就是c / d为整数,即c是gcd(a,b)的倍数

如果有解,那么令 K = c/d;

那么,对方程aX+bY = d;假设有拓展欧几里得求出一组解为(X0,Y0),那么aX0+bY0 = d;等式两边同时乘以K,即K( aX0+bY0 ) = dK = c;由恒等关系,原方程的解(x0,y0):

X0 = KX0 = c/d * X0,y0 = KY0 = c/d * Y0。
不定方程的通解

若(x0,y0)是不定整数方程ax+by = c的一组解,则他的任意整数解都可以表示成(x0+ kb’, y0-ka’),其中a’ = a/gcd(a,b), b’ = b/gcd(a,b).

y -= (a/b) * x

对于这段代码当时是无法理解的,经过在自己在网上看别人写是博客文章和查阅资料终于搞明白这式子是怎么来的啦~
里先说明一下我的一些规则,x,y表示第一次递归时的值,x1,y1表示第二次递归时的值。那么

gcd(a,b)==gcd(b,a%b),同时都代入式1,有ax+by==bx1+(a%b) y1。将右边变形一下

bx1+(a%b) y1==bx1+(a-(a/b) b) * y1==ay1+b(x1-(a/b) * y1),最终得到ax+by==ay1+b(x1-(a/b) * y1)

也就是说,上一深度的x等于下一深度的y1,上一深度的y等于下一深度的x1-(a/b) * y1。 需要注意,上面推导时用的除法都是整型除法
对于 y = y - (a/b) * x; 由 ax+by==a*y1+b*(x1-(a/b) * y1)根据对应关系可以得出 x = y1; y = (x1-(a/b) * y1); 根据x = y1也就得出 x1 = y (其实这里就是递归的一个先后的关系)。最终得出y -= (a/b) * x的结论.

记a=10*,b=10* ,c=100*(x1y2-x2y1), g=gcd

题目应用

那么用扩展欧几里德可以得到aX+bY=gcd的一组解。注意,这里得到的一组解仅保证abs取到最小值

题目描述

一个双六上面有向前向后无限延续的格子,每个格子都写

有整数。其中0号格子是起点,1 号格子是终点。而骰子上只有a,b,-a,-b四个整数,

所以根据a和b的值的不同,有可能无法到达终点。现在的问题是掷出a,b,-a,-b各

多少次可以达到终点呢?
掷出的四个整数各多少次可以达到终点呢?如果解不唯一,输出任何一组就好,如果无解,输出-1。

判断需要求解的方程是否有解,只需要判断c%gcd==0是否成立即可。

样例输入

a = 4, b = 11

那么就可以得到需要求解的方程的一组解:X0=X*c/g, Y0=Y*c/g

样例输出

3 -1

此时就可以对区间有几个解进行计算了。

思路分析

这个问题其实就是一道裸的扩展欧几里得算法,翻译过来就是求整数x、y使得ax+by=1。

另外,因为之前扩展欧几里德写的少,所以xjb写了一发暴力,此处贴上代码。

AC代码

# include <iostream>
# include <cstdio>
# include <string>
# include <algorithm>
using namespace std;

int gcd(int a,int b)
{
  if (b == 0) return a;
  return gcd(b,a%b);
}
int extgcd(int a,int b,int &x,int &y)
{
  int d = a;
  if (b != 0)
  {
    d = extgcd(b,a % b,y,x);
    y -= (a / b) * x;
  }
  else
  {
    x = 1; y = 0;
  }
  return d;
}
int main()
{
  int a,b;
  int x,y;
  while(scanf("%d%d",&a,&b)!=EOF)
  {
    extgcd(a,b,x,y);
    if (gcd(a,b)!=1)
    printf("impossible!n");
    else
    printf("%d %dn",x,y);
  }
  return 0;
}

正解:

图片 1图片 2

 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 int T; 5 LL x[2], y[2]; 6 void read(LL &x) 7 { 8     LL a, b; 9     scanf("%lld.%lld", &a, &b);10     x = a * 10 + b;11 }12 void exgcd(LL a, LL b, LL& g, LL& x, LL& y)13 {14     if  g = a, x = 1, y = 0;15     else exgcd(b, a%b, g, y, x), y -= x * (a / b);16 }17 LL solve()18 {19     LL ans = 0;20     for (int i = 0; i < 2; i++)read, read;21     if (x[0] > x[1] || x[0] == x[1] && y[0] > y[1]) {22         swap(x[0], x[1]);23         swap(y[0], y[1]);24     }25 26     if (x[0] == x[1]) {27         if (x[0] % 10)return 0;28         return max(0LL, y[1] / 10 - (y[0] + 9) / 10 + 1);29     }30     if (y[0] == y[1]) {31         if (y[0] % 10)return 0;32         return max(0LL, x[1] / 10 - (x[0] + 9) / 10 + 1);33     }34 35     LL a, b, g, X, Y;36     a = (y[1] - y[0]) * 10;37     b = (x[0] - x[1]) * 10;38     exgcd(a, b, g, X, Y);39     LL c = x[0] * y[1] - x[1] * y[0];40     if return 0;41     X = X * c / g;42     x[0] = (x[0] + 9) / 10;43     x[1] = x[1] / 10;44     if (x[0] > x[1])return 0;45     LL st = abs(b / g);46     LL cx = X - (X - x[0]) / st * st;47     if (cx < x[0])cx += st;48     if (cx > x[1])return 0;49     return (x[1] - cx) / st + 1;50 }51 int main()52 {53     //freopen("in.txt", "r", stdin);54     //freopen("out.txt", "w", stdout);55     scanf("%d", &T);56     while (T--) {57         printf("%lldn", solve;58     }59 }

View Code

暴力:

图片 3图片 4

 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL ; 4 int T; 5 LL x[2], y[2]; 6 LL gcd(LL a, LL b) 7 { 8     return b == 0 ? a : gcd(b, a%b); 9 }10 void read(LL &x)11 {12     LL a, b;13     scanf("%lld.%lld", &a, &b);14     x = a * 10 + b;15 }16 int main()17 {18     scanf("%d", &T);19     while (T--) {20         for (LL i = 0; i < 2; i++)read, read;21         /*for (int i = 0; i < 2; i++) {22             x[i] =  % 200 + 1) * 10;23             y[i] =  % 200 + 1) * 10;24         }*/25         //printf("%d %d %d %dn", x[0], y[0], x[1], y[1]);26         if (x[0] > x[1] || x[0] == x[1] && y[1] > y[0]) {27             swap(x[0], x[1]);28             swap(y[0], y[1]);29         }30         if (x[0] == x[1] && (x[0] % 10) || y[0] == y[1] && (y[0] % 10)) {31             printf("0n");32             continue;33         }34         if (x[0] == x[1] && y[0] == y[1]) {35             if (x[0] % 10 == 0 && y[0] % 10 == 0) {36                 printf("1n");37             }38             else printf("0n");39             continue;40         }41         LL dx = abs(x[0] - x[1]);42         LL dy = abs(y[0] - y[1]);43         LL g = gcd;44         LL st = dx / g;45         LL cx = x[0], cy = y[0];46         LL ans = 0;47         for (LL i = 0; i <= 100 && cx <= x[1] && (cy - y[0])*(cy - y[1]) <= 0; i++) {48             if (cx % 10 == 0 && cy % 10 == 0) {49                 long long gc = gcd(gcd(st, 10), gcd(dy / g, 10));50                 LL t = 10 / gcd(gcd(st, 10), gcd(dy / g, 10));51                 if ans = 1 + (x[1] - cx) / (t*st);52                 else ans = abs(y[1] - cy) / (dy / g * t) + 1;53                 break;54             }55             cx += st;56             cy += (y[1] - y[0]) / g;57         }58         printf("%lldn", ans);59     }60 }

View Code

---恢复内容结束---

本文由澳门太阳娱乐手机登录发布于 资质荣誉,转载请注明出处:扩展欧几里德算法及其应用

关键词: