POJ1061 (青蛙的约会)做题笔记

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接:http://poj.org/problem?id=1061
这题是拓展欧几里得算法。

裴蜀等式

任何整数a、b和m,关于未知数x和y的线性丢番圆方程(称为裴蜀等式):
ax+by=m
有整数解时当且仅当m是a和b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解,每组解x、y都称为裴蜀数
——引用自维基百科

若方程ax+by=m的一组整数解为(x0,y0),则它的任意整数解都可以写成(x0+kb’,y0-ka’),其中a’=a/gcd(a,b),b’=b/gcd(a,b),k取任意整数

模线线性方程组

ax≡b(mod n)
ax=b+ny
ax-ny=b 进而转化为裴蜀等式
补充:当b等于1时模线性方程组的解是a关于模n的逆,a关于模n的逆存在当且仅当a和n互质,此时方程有唯一解

题目思路

根据题意可以写出等式(x+km)%L=(y+kn)%L
而这样的式子有一个性质a%L=b%L ==> (a+c)%L=(b+c)%L
因而可以得出(k(m-n))%L=(y-x)%L
k(m-n)≡y-x(mod L) 接下来就可以用解模线性方程组的方法来做了
需要注意m-n必须是非负的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long LL;
int d;
LL x,y;
void exgcd(int a,int b,int &d,LL &x,LL &y) {
if (!b) { d=a;x=1;y=0; } else
{ exgcd(b,a%b,d,y,x);y-=x*(a/b); }
}
bool linear_equation(int a,int b,int c) {
exgcd(a,b,d,x,y);
if (c%d) return 0;
x*=c/d;
y*=c/d;
return 1;
}
int main() {
int m,n,a,b,L;
bool opt;
scanf("%d%d%d%d%d",&a,&b,&m,&n,&L);
if (m<n) {
std::swap(m,n);
std::swap(a,b);
}
opt=linear_equation(m-n,L,b-a);
if (opt) {
while (x>0) x-=L/d;
while (x<0) x+=L/d;
printf("%lld",x);
}
else printf("Impossible");
}