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");
}