信奥赛C++提高组csp-s之数论基础专题课：从同余到分数模运算5(案例实践：青蛙的约会)
课程目标
第三部分：案例实战（青蛙的约会）
研究案例：P1516 青蛙的约会
题目描述
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经
0
0
0 度处为原点，由东往西为正方向，单位长度
1
1
1 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是
x
x
x，青蛙 B 的出发点坐标是
y
y
y。青蛙 A 一次能跳
m
m
m 米，青蛙 B 一次能跳
n
n
n 米，两只青蛙跳一次所花费的时间相同。纬度线总长
L
L
L 米。现在要你求出它们跳了几次以后才会碰面。
输入格式
输入只包括一行五个整数
x
,
y
,
m
,
n
,
L
x,y,m,n,L
x,y,m,n,L。
输出格式
输出碰面所需要的次数，如果永远不可能碰面则输出一行一个字符串 Impossible。
输入输出样例 1
输入 1
1 2 3 4 5
输出 1
4
说明/提示
对于
100
%
100\\%
100% 的数据，
1
≤
x
,
y
,
m
,
n
≤
2
×
10
9
1 \\le x, y, m, n \\le 2 \\times 10^9
1≤x,y,m,n≤2×109，
x
≠
y
x \\ne y
x=y，
1
≤
L
≤
2.1
×
10
9
1 \\le L \\le 2.1 \\times 10^9
1≤L≤2.1×109。
思路分析
本题是经典的线性同余方程问题。两只青蛙在长度为 L 的环上跳，起始坐标分别为 x 和 y，步长分别为 m 和 n，同时同向朝西跳。问跳多少次后相遇。
- 设跳了 t 次后相遇，此时青蛙 A 的位置为
(
x
+
m
t
)
m
o
d
L
(x + m t) \\bmod L
(x+mt)modL，青蛙 B 的位置为(
y
+
n
t
)
m
o
d
L
(y + n t) \\bmod L
(y+nt)modL。 - 相遇条件：
(
x
+
m
t
)
≡
(
y
+
n
t
)
(
m
o
d
L
)
(x + m t) \\equiv (y + n t) \\pmod{L}
(x+mt)≡(y+nt)(modL)。 - 移项得：
(
m
−
n
)
t
≡
(
y
−
x
)
(
m
o
d
L
)
(m – n) t \\equiv (y – x) \\pmod{L}
(m−n)t≡(y−x)(modL)。
令 (a = m – n)，(c = y – x)，则方程化为：
a
t
≡
c
(
m
o
d
L
)
a t \\equiv c \\pmod{L}
at≡c(modL) 这是一个标准的一元线性同余方程。
关键步骤
处理负数：在模运算中，通常将系数转化为非负剩余，避免扩展欧几里得算法中的符号混乱。因此先对 (a) 和 (c) 取模：
a
=
(
(
m
−
n
)
m
o
d
L
+
L
)
m
o
d
L
,
c
=
(
(
y
−
x
)
m
o
d
L
+
L
)
m
o
d
L
a = ((m – n) \\bmod L + L) \\bmod L,\\quad c = ((y – x) \\bmod L + L) \\bmod L
a=((m−n)modL+L)modL,c=((y−x)modL+L)modL 这样
0
≤
a
,
c
<
L
0 \\le a, c < L
0≤a,c<L。
特殊情况 (a = 0)：
- 若 (a = 0)，则方程变为
0
⋅
t
≡
c
(
m
o
d
L
)
0 \\cdot t \\equiv c \\pmod{L}
0⋅t≡c(modL)。 - 若 (c = 0)，说明任何 t 都满足，但实际含义是两只青蛙起始就在同一位置（模 L 意义下），所以 t = 0。
- 若 (
c
≠
0
c \\neq 0
c=0)，则无解，输出 Impossible。
一般情况：利用扩展欧几里得算法求解。
- 求
g
=
gcd
(
a
,
L
)
g = \\gcd(a, L)
g=gcd(a,L)，并找到一组整数解(
t
0
,
k
0
)
(t_0, k_0)
(t0,k0) 满足a
t
0
+
L
k
0
=
g
a t_0 + L k_0 = g
at0+Lk0=g。 - 原方程有解当且仅当
g
∣
c
g \\mid c
g∣c。若不整除，输出 Impossible。
构造通解：
- 方程两边同时除以 (g) 得到：
a
g
t
≡
c
g
(
m
o
d
L
g
)
\\frac{a}{g} t \\equiv \\frac{c}{g} \\pmod{\\frac{L}{g}}
gat≡gc(modgL) 此时gcd
(
a
/
g
,
L
/
g
)
=
1
\\gcd(a/g, L/g) = 1
gcd(a/g,L/g)=1，因此 a/g 在模 L/g 下有逆元。 - 一个特解为
t
=
t
0
⋅
(
c
/
g
)
t = t_0 \\cdot (c/g)
t=t0⋅(c/g)（因为a
t
0
≡
g
(
m
o
d
L
)
a t_0 \\equiv g \\pmod{L}
at0≡g(modL)，乘以 c/g 得a
⋅
(
t
0
⋅
c
/
g
)
≡
c
(
m
o
d
L
)
a \\cdot (t_0 \\cdot c/g) \\equiv c \\pmod{L}
a⋅(t0⋅c/g)≡c(modL)。 - 通解形式：
t
=
t
0
⋅
(
c
/
g
)
+
k
⋅
(
L
/
g
)
t = t_0 \\cdot (c/g) + k \\cdot (L/g)
t=t0⋅(c/g)+k⋅(L/g)，其中k
∈
Z
k \\in \\mathbb{Z}
k∈Z。
求最小非负解：
- 令
m
o
d
=
L
/
g
mod = L / g
mod=L/g，则最小非负解为t
=
(
t
0
⋅
(
c
/
g
)
)
m
o
d
m
o
d
t = (t_0 \\cdot (c/g)) \\bmod mod
t=(t0⋅(c/g))modmod，再调整为非负数。 - 注意乘法
t
0
⋅
(
c
/
g
)
t_0 \\cdot (c/g)
t0⋅(c/g) 可能溢出，故采用取模运算避免：先分别对t
0
和
c
/
g
t_0 和 c/g
t0和c/g 取模 mod，再相乘取模。即：t
=
(
(
t
0
m
o
d
m
o
d
)
×
(
(
c
/
g
)
m
o
d
m
o
d
)
)
m
o
d
m
o
d
t = ( (t_0 \\bmod mod) \\times ((c/g) \\bmod mod) ) \\bmod mod
t=((t0modmod)×((c/g)modmod))modmod - 最后若结果为负，加上 (mod) 使其非负（实际取模后已保证
0
≤
t
<
m
o
d
0 \\le t < mod
0≤t<mod）。
输出：得到的 t 即为所需跳的次数。
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 使用 long long 避免溢出
// 扩展欧几里得：求 a*x + b*y = gcd(a,b) 的一组整数解 (x,y)
// 返回 gcd(a,b)（保证非负）
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1; y = 0;
return a > 0 ? a : –a; // 确保 gcd 为正数
}
ll g = exgcd(b, a % b, y, x); // 递归求解
y -= a / b * x; // 回溯更新 y
return g;
}
int main() {
ll x, y, m, n, L;
cin >> x >> y >> m >> n >> L;
// 将系数化为模 L 下的非负剩余
ll a = ((m – n) % L + L) % L; // a = (m-n) mod L
ll c = ((y – x) % L + L) % L; // c = (y-x) mod L
// 特殊情况：a == 0
if (a == 0) {
if (c == 0) cout << 0 << endl; // 已在同一点
else cout << "Impossible" << endl;
return 0;
}
ll t0, k0; // 用于存储 exgcd 得到的特解
ll g = exgcd(a, L, t0, k0); // g = gcd(a, L)
// 无解条件：c 不能被 g 整除
if (c % g != 0) {
cout << "Impossible" << endl;
return 0;
}
ll mod = L / g; // 通解的周期
// 计算 t = t0 * (c/g) 对 mod 取模的最小非负数
// 为避免乘法溢出，分步取模
ll t = ( (t0 % mod) * ((c / g) % mod) ) % mod;
// 调整到 [0, mod-1] 区间（取模结果已在区间内，但确保非负）
t = (t + mod) % mod;
cout << t << endl;
return 0;
}
功能分析
本程序实现了“青蛙的约会”问题的求解，主要功能模块如下：
(
m
−
n
)
t
≡
(
y
−
x
)
(
m
o
d
L
)
(m-n)t \\equiv (y-x) \\pmod{L}
(m−n)t≡(y−x)(modL)的系数化为模 L 下的非负剩余，避免后续负数处理。
m
≡
n
(
m
o
d
L
)
m \\equiv n \\pmod{L}
m≡n(modL) 时，若初始位置相同则答案为 0，否则无解。
gcd
(
a
,
L
)
\\gcd(a, L)
gcd(a,L) 及一组特解，时间复杂度
O
(
log
L
)
O(\\log L)
O(logL)。
gcd
(
a
,
L
)
\\gcd(a, L)
gcd(a,L) 整除，若不能则输出 Impossible。
- 利用公式
t
=
t
0
⋅
(
c
/
g
)
(
m
o
d
L
/
g
)
t = t_0 \\cdot (c/g) \\pmod{L/g}
t=t0⋅(c/g)(modL/g) 得到最小非负整数解。 - 通过两次取模运算避免乘法溢出
t
0
t_0
t0 和c
/
g
c/g
c/g 均可能较大，但取模后相乘仍在 long long 范围内）。
复杂度分析
- 时间复杂度：
O
(
log
L
)
O(\\log L)
O(logL)，单次递归调用。 - 空间复杂度：
O
(
1
)
O(1)
O(1)，仅使用常数个变量。
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》： https://blog.csdn.net/weixin_66461496/category_13113932.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}
1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html
4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}
