本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15816368.html

上课记的，有点乱

「一本通 6.4 例 1」青蛙的约会

式子推倒

x+mt≡y+nt(modL)\Large x+mt\equiv y+nt\pmod L

mt−nt≡y−x(modL)\Large mt-nt\equiv y-x \pmod L

(m−n)t≡y−x(modL)\Large (m-n)t\equiv y-x \pmod L

t≡(y−x)×(m−n)−1(modL)\Large t\equiv (y-x)\times (m-n)^{-1} \pmod L

逆元：若 x×x−1≡(modL)x\times x^{-1}\equiv \pmod L，则称 x−1x^{-1} 为 xx 的逆元。

假设 (m−n)=k(m-n)=k，现在求 k−1k^{-1} 。

拓展欧几里得

假设有 ax+by=1ax+by=1

当 gcd⁡(a,b)=1\gcd(a,b)=1，则有解，不然可以提一个 gcd(a,b)gcd(a,b) 出来。

设 r=a mod br=a\bmod b

bx′+ry′=1\Large bx'+ry'=1

这样子不断模下去，必然会出现 r=0,b=1r=0, b=1，此时 x=y=1x=y=1 即可。

现在我们假设知道：

ax+by=1\Large ax+by=1

bx′+ry′=1\Large bx'+ry'=1

设 p=abp=\frac{a}{b}，r=ar=a%b，a=pb+ra=pb+r，

带入得：

(pb+r)x+by=1\Large (pb+r)x+by=1

pbx+rx+by=1\Large pbx+rx+by=1

b(px+y)+rx=1\Large b(px+y)+rx=1

此时我们发现这条式子与 bx′+ry′=1bx'+ry'=1 很像，于是得到：

x=y′\Large x=y'

y=x′−px\Large y=x'-px

拓欧求逆元

ax mod b+by mod b=1ax\bmod b+by\bmod b=1

ax mod b=1ax\bmod b=1

所以 xx 是 a mod ba\bmod b 下的逆元。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void exgcd(int a, int b, int x, int y)
{
	if(b==0) x=y=1; 
	else
	{
		gcd(b, a%b, y, x); 
		y-=a/b*x; 
	}
}

int main()
{
	a=((m-n)%L+L)%L; //求a的逆元
	exgcd(a, L, x, y); 
}

题目解法

ax+by=cax+by=c有解，ax+byax+by 总是 gcd⁡(a,b)\gcd(a,b) 的倍数，所以 cc 也要是 gcd⁡(a,b)\gcd(a,b) 的倍数。

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
#include<bits/stdc++.h>
using namespace std; 
#define int long long
int n, m, i, j, k; 
int x, y, p, q, L, a, b, c; 

void exgcd(int a, int b, int &x, int &y)
{
	if(b==0) x=c/a, y=0; 
	else
	{
		exgcd(b, a%b, y, x); 
		y-=a/b*x; 
	}
}//exgcd直接解方程

signed main()
{
	cin>>x>>y>>m>>n>>L;  
	a=((m-n)%L+L)%L;
	c=((y-x)%L+L)%L; 
	exgcd(a, L, p, q); 
	p=(p%L+L)%L; 
	if(a*p%L!=c) return printf("Impossible"), 0; 
	printf("%lld", p); 
	return 0; 
}