POJ1061 青蛙的约会（线性同余方程）

线性同余方程$ ax \equiv b \pmod n$可以用扩展欧几里得算法求解。

这一题假设青蛙们跳t次后相遇，则可列方程：

$$ Mt+X \equiv Nt+Y \pmod L$$
$$ (M-N)t \equiv Y-X \pmod L$$

于是就构造出一个线性同余方程，即可对t求解，解出最小非负整数解。

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define mod(x,y) (((x)%(y)+(y))%(y))

 #define lld long long

 //a*x+b*y=gcd(a,b)

 lld exgcd(lld a,lld b,lld &x,lld &y){

     if(b==){

         x=; y=;

         return a;

     }

     lld d=exgcd(b,mod(a,b),x,y);

     lld t=y;

     y=x-a/b*y;

     x=t;

     return d;

 }

 //ax¡Ôb (mod n)

 lld MLES(lld a,lld b,lld n){

     lld x,y;

     lld d=exgcd(a,n,x,y);

     if(b%d) return -;

     return mod(x*(b/d),n/d);

 }

 int main(){

     lld x,y,m,n,l;

     scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);

     lld res=MLES(m-n,y-x,l);

     if(res==-) puts("Impossible");

     else printf("%lld",res);

     return ;

 }

巴特西

POJ1061 青蛙的约会（线性同余方程）

最新文章

热门文章