P1516 青蛙的约会(exgcd)

本文主要是介绍P1516 青蛙的约会(exgcd)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一些前置知识：

1.扩展欧几里得算法：

                                         ax+by=gcd(a,b)

方程一个可行的解（x1,y1）求法：

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

 2.由ax+by=gcd(a,b) 的解推出 ax+by=n  的一个可行解（x0,y0）:

3.由ax+by=n   的解（x0,y0）推其通解：

4.在通解中找最小正整数解的小技巧：

   设y=t*x+z(t、z为常数，x为变量) ,则y 的最小正整数解为：

y`=(z%t+t)%t;

正式进入题解：

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long int exgcd(int a,int b,int &x,int &y) 
{if(!b){x=1,y=0; return a;}int d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}signed main()
{int x,y,m,n,l,x0,y0; cin>>x>>y>>m>>n>>l;int a=m-n,b=y-x;if(a<0) a=-a,b=-b;//注意gcd仅仅对正整数有意义，故要将系数化为正数int d=exgcd(a,l,x0,y0);//扩欧if(b%d) cout<<"Impossible";//判断原方程是否有解else {int k=l/d;cout<<(x0*(b/d)%k+k)%k;//求最小正整数解}}

24/8/29

这篇关于P1516 青蛙的约会(exgcd)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---