欧几里得算法求解二元一次方程及其简单应用"/>
扩展欧几里得算法求解二元一次方程及其简单应用
4月9号就要蓝桥杯,最近在写蓝桥杯的题,今天遇到了两个题比较类似,同样都是利用的扩展欧几里得算法求解二元一次方程,在这里进行简单的总结。
扩展欧几里得算法:已知整数a,b,求出a和b的最大公约数,同时可以求出二元一次方程关于x和y的一组整数解,详细解释可以看扩展欧几里得算法(百度百科)
对于扩展欧几里得算法:
① 当b=0时,,此时,所以此时x=1,y=0。
②当b不等于0时,由于
所以 所以先求出x',y'再代入公式
代码如下:
int exgcd(int a,int b,int &x,int &y)
{if(!b){x=1;y=0;return a;}int x2,y2;int d=exgcd(b,a%b,x2,y2);x=y2;y=x2-a/b*y2;return d;
}
注意:有时候题目中的数据范围比较大,所以需要改为long long。
将方程改为试用范围更广的情况:。对于该方程,设,该方程有整数解当且仅当d|c,求解方法如下:
用扩展欧几里得求出 的解,则。
故而特解为 ,而通解 = 特解 + 齐次解,而齐次解即为方程
的解,故而通解为 x=x′+k∗b/d,x=y′−k∗a/d, k∈z。
第一道题:AcWing 1299. 五指山
题目如下:
大圣在佛祖的手掌中。
我们假设佛祖的手掌是一个圆圈,圆圈的长为 n,逆时针记为:0,1,2,…,n−10,1,2,…,n−1,而大圣每次飞的距离为 d。
现在大圣所在的位置记为 x,而大圣想去的地方在 y。
要你告诉大圣至少要飞多少次才能到达目的地。
注意:孙悟空的筋斗云只沿着逆时针方向翻。
输入格式
有多组测试数据。
第一行是一个正整数 TT,表示测试数据的组数;
每组测试数据包括一行,四个非负整数,分别为如来手掌圆圈的长度 n,筋斗所能飞的距离 d,大圣的初始位置 x和大圣想去的地方 y。
输出格式
对于每组测试数据,输出一行,给出大圣最少要翻多少个筋斗云才能到达目的地。
如果无论翻多少个筋斗云也不能到达,输出 Impossible。
数据范围
2<n<10^9,
0<d<n,
0≤x,y<n
输入样例:
2
3 2 0 2
3 2 0 1
输出样例:
输出样例:
1
2
题解:
对于这个题而言,可以从题目中提取出公式(x+b*d)%n=y,这个题就是在求解b的值,可以转化为x+b*d=y+n*a,其中d和n为已知的常量,转化为b*d-n*a=y-x,所以可以求解方程b*d+n*a=gcd(d,n)的解,然后找这两个方程的关系,从而求出最小k的值。
求出方程中a,b的值,然后扩大(y-x)/gcd(n,d)倍,因为这道题在求解b的值,所以利用方程
b = b0+k*(n/gcd(n,d)),k∈Z。由于k可能为负数,所以b可能变为负数,这道题要求为正,所以利用取余的特性最小值为(b%n+n)%n。
代码如下:
#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 x2,y2;ll d=exgcd(b,a%b,x2,y2);x=y2;y=x2-a/b*y2;return d;}
}
int main()
{int t;cin>>t;while(t--){ll n,d,x,y;scanf("%lld%lld%lld%lld",&n,&d,&x,&y);ll a,b;int gcd=exgcd(n,d,a,b);if((y-x)%gcd!=0){puts("Impossible");}else {b*=(y-x)/gcd;n/=gcd;//b=b0-n/gcd(n,d).cout<<((b%n)+n)%n<<endl;}}
}
第二道题:Acwing:1301. C 循环
题目如下:
对于 C 语言的循环语句,形如:
for (variable = A; variable != B; variable += C)statement;
请问在 k位存储系统中循环几次才会结束。
若在有限次内结束,则输出循环次数。否则输出死循环。
输入格式
多组数据,每组数据一行四个整数 A,B,C,k。
读入以 0 0 0 0 结束。
输出格式
若在有限次内结束,则输出循环次数。
否则输出 FOREVER。
数据范围
1≤k≤32,
0≤A,B,C<2^k
输入样例:
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
输出样例:
0
2
32766
FOREVER
题解:
这个题中的k位存储器,即计算机的存储方式,所有的数值的二进制位仅保留最后k位,所以相当于对2^k求余数。
从题目中提取出信息,可以提炼出以下公式(A + xC)mod 2^k = B ,所以这道题本质上是在求解x的值,可以用上一道题的方法进行转化求解。
代码如下:
#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;}ll x2,y2;ll d=exgcd(b,a%b,x2,y2);x=y2;y=x2-a/b*y2;return d;}
int main()
{ll a,b,c,k;while(cin>>a>>b>>c>>k,a||b||c||k){ll d=1ll<<k;ll x,y;ll gcd=exgcd(c,d,x,y);if((b-a)%gcd!=0){puts("FOREVER");}else {x*=(b-a)/gcd;d/=gcd;cout<<(x%d+d)%d<<endl;}}
}
总结一下:对于类似的题目,可以提取出公式,给定ax+by=c中的常量a和b求解x或者y的最小值,在扩大一定的倍数,利用通解公式即可求出最终答案。
更多推荐
扩展欧几里得算法求解二元一次方程及其简单应用
发布评论