扩展欧几里德算法

模板

void exgcd(int a,int b) { if (b==0) { x=1; y=0; return ; //得到gcd(b,0)时到达边界值 } // else { exgcd(b,a%b); int k=x; x=y; y=k-(a/b)*y; //根据上方推出的公式进行递归求出结果 } return ; }

P1082 同余方程 题目描述 求关于 xx的同余方程 ax≡1(mod b) 的最小正整数解。

输入格式 一行，包含两个正整数 a,ba,b，用一个空格隔开。

输出格式 一个正整数 x_0x 0 ​ ，即最小正整数解。输入数据保证一定有解。

输入输出样例 输入 #1 复制

3 10

输出 #1 复制

7

说明/提示 【数据范围】

对于 40%的数据，2 ≤b≤ 1,0002≤b≤1,000；

对于 60%的数据，2 ≤b≤ 50,000,0002≤b≤50,000,000；

对于 100%的数据，2 ≤a, b≤ 2,000,000,0002≤a,b≤2,000,000,000。

NOIP 2012 提高组 第二天 第一题

对于同余方程ax ≡ 1 (mod b)，如果转化为我们易懂的语言就是 求满足ax%b=1，1%b=1最小正整数解。

#include <cstdio> #include <iostream> using namespace std; int a,q; int x,y; void exgcd(int a,int b) { if (b==0) { x=1; y=0; return ; //得到gcd(b,0)时到达边界值 } // else { exgcd(b,a%b); int k=x; x=y; y=k-(a/b)*y; //根据上方推出的公式进行递归求出结果 } return ; } int main() { scanf("%d%d",&a,&q); exgcd(a,q); printf("%lld",(x+q)%q); return 0; }

exgcd（拓展欧几里得） 1.回顾辗转相除法求最大公倍数：

（辗转相除法和下面所讲到的算法里面的m和n没什么关系可正可负 更没有大小关系的区分）

代码：

#include<stdio.h> int gcd(int a,int b) { int temp; if(b==0){ return a; // b=0 满足关系跳出循环，此时a的值就是最大公约数 } return gcd(b,a%b); } int main() { int a,b; scanf("%d%d",&a,&b); printf("%d\n",gcd(a,b)); return 0; }

2.exgcd：

a.求二元一次方程的一组特解：

原理：

•ax+by=gcd(a,b) •∵ gcd(a,b) = gcd(b,a%b) •∴ ax1+by1 = bx2+(a%b)y2 //可以知道 a在被替换成了b，b被替换成了a%b •则 ax1+by1 = bx2+(a-a/b*b)y2 •∴ ax1+by1 = ay2+b(x2-a/b*y2) •∴ x1=y2 y1=(x2-a/b*y2) //这一步的x等于上一步的y，y等于(x2-a/b*y2) x2 y2 代表上一步的x和y •当b==0时，ax+by = gcd(a,b) = a •∴ x=1 , y=0;

Code：

#include<stdio.h> int GCD; int gcd(int a,int b,int &x,int &y) //&x 类似于指针在c++函数调用中可以将x的值改变 { if(!b){ ② x=1;y=0;return a; } //调用的函数运行顺序 GCD=gcd(b,a%b,y,x); ① //调用函数时的&不能加，错误不太容易发现 y-=a/b*x; 3 4 ... return GCD; //最后返回的GCD的含义其实就是a和b的最大公约数 } int main() { int a,b,x,y; scanf("%d%d",&a,&b); GCD=gcd(a,b,x,y); printf("%d %d %d",x,y,GCD); return 0; }

b.求通解：

•ax + by = gcd(a,b) 的解集 •首先可以肯定它一定有解且解的数量无限 •我们可以找出式子可以加减的最小元 即最小公倍数lcm •若x +- b/gcd y-+ a/gcd 则等式依然成立 //如果x后为+ 则y后为- •便可得知解集

c.判断ax+by=c是否有解:

只要c为gcd（a，b）的倍数，就有无数组解

例： 38x+8y=gcd(38,8)=2; ①

如果此时c=6 即：38x+8y=6； ②

计算②式特解的方法： 先算出①式的特解 然后将x和y同时乘于6 / gcd（38，8）就能得到一组特解；

d.求最小整数解：

//用于解决ax+by=c类的求最小整数解 GCD=exgcd(a,b); x=c/GCD; //如果非上面的类型而直接是=gcd(a,b) 可将这一步去掉即可 t=b/GCD: if(t<0){ t=-t; //防止b/GCD为负数 } x=(x%t+t)%t;

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

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

输入格式 输入只包括一行5个整数x，y，m，n，L

其中0<x≠y < =2000000000，0 < m、n < =2000000000，0 < L < =2100000000。

输出格式 输出碰面所需要的天数，如果永远不可能碰面则输出一行"Impossible"。

输入输出样例 输入 #1 复制

1 2 3 4 5

输出 #1 复制

4

Code: 套用公式 a=n-m; b=l;c=x-y; 然后求最小整数解：

//用于解决ax+by=c类的求最小整数解 GCD=exgcd(a,b); x=c/GCD; //如果非上面的类型而直接是=gcd(a,b) 可将这一步去掉即可 t=b/GCD: if(t<0){ t=-t; //防止b/GCD为负数 } x=(x%t+t)%t; #include<bits/stdc++.h> using namespace std; typedef long long LL; LL Exgcd(LL a,LL b,LL &x,LL &y) { if(b==0){ x=1; y=0; return a; } else{ LL r=Exgcd(b,a%b,x,y); LL t; t=x; x=y; y=t-a/b*y; return r; //r是公倍数 } } int main() { LL x,y,m,n,l; cin>>x>>y>>m>>n>>l; LL a=n-m; LL b=l; LL c=x-y; if(a<0){ a=-a; c=-c; } LL x0,y0; LL z=Exgcd(a,b,x0,y0); if(c%z==0){ LL k=l/z; printf("%lld\n",((x0*c/z)%k+k)%k);//求最小整数解 } else{ printf("Impossible\n"); } return 0; }