信奥赛C提高组csp-s之数论基础专题课从同余到分数模运算5(案例实践青蛙的约会)课程目标理清脉络理解同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算之间的逻辑关系。掌握核心熟练运用扩展欧几里得算法求解不定方程及逆元。实战应用能够解决相关的数论模板题和简单变式题。第三部分案例实战青蛙的约会研究案例P1516 青蛙的约会题目描述两只青蛙在网上相识了它们聊得很开心于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上于是它们约定各自朝西跳直到碰面为止。可是它们出发之前忘记了一件很重要的事情既没有问清楚对方的特征也没有约定见面的具体位置。不过青蛙们都是很乐观的它们觉得只要一直朝着某个方向跳下去总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙你被要求写一个程序来判断这两只青蛙是否能够碰面会在什么时候碰面。我们把这两只青蛙分别叫做青蛙 A 和青蛙 B并且规定纬度线上东经0 00度处为原点由东往西为正方向单位长度1 11米这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是x xx青蛙 B 的出发点坐标是y yy。青蛙 A 一次能跳m mm米青蛙 B 一次能跳n nn米两只青蛙跳一次所花费的时间相同。纬度线总长L LL米。现在要你求出它们跳了几次以后才会碰面。输入格式输入只包括一行五个整数x , y , m , n , L x,y,m,n,Lx,y,m,n,L。输出格式输出碰面所需要的次数如果永远不可能碰面则输出一行一个字符串Impossible。输入输出样例 1输入 11 2 3 4 5输出 14说明/提示对于100 % 100\%100%的数据1 ≤ x , y , m , n ≤ 2 × 10 9 1 \le x, y, m, n \le 2 \times 10^91≤x,y,m,n≤2×109x ≠ y x \ne yxy1 ≤ L ≤ 2.1 × 10 9 1 \le L \le 2.1 \times 10^91≤L≤2.1×109。思路分析本题是经典的线性同余方程问题。两只青蛙在长度为 L 的环上跳起始坐标分别为 x 和 y步长分别为 m 和 n同时同向朝西跳。问跳多少次后相遇。设跳了 t 次后相遇此时青蛙 A 的位置为( x m t ) m o d L (x m t) \bmod L(xmt)modL青蛙 B 的位置为( y n t ) m o d L (y n t) \bmod L(ynt)modL。相遇条件( x m t ) ≡ ( y n t ) ( m o d L ) (x m t) \equiv (y n t) \pmod{L}(xmt)≡(ynt)(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 La((m−n)modLL)modL,c((y−x)modLL)modL这样0 ≤ a , c L 0 \le a, c L0≤a,cL。特殊情况 (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 0c0)则无解输出Impossible。一般情况利用扩展欧几里得算法求解。求g gcd ⁡ ( a , L ) g \gcd(a, L)ggcd(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 gat0​Lk0​g。原方程有解当且仅当g ∣ c g \mid cg∣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}}ga​t≡gc​(modgL​)此时gcd ⁡ ( a / g , L / g ) 1 \gcd(a/g, L/g) 1gcd(a/g,L/g)1因此 a/g 在模 L/g 下有逆元。一个特解为t t 0 ⋅ ( c / g ) t t_0 \cdot (c/g)tt0​⋅(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)tt0​⋅(c/g)k⋅(L/g)其中k ∈ Z k \in \mathbb{Z}k∈Z。求最小非负解令m o d L / g mod L / gmodL/g则最小非负解为t ( t 0 ⋅ ( c / g ) ) m o d m o d t (t_0 \cdot (c/g)) \bmod modt(t0​⋅(c/g))modmod再调整为非负数。注意乘法t 0 ⋅ ( c / g ) t_0 \cdot (c/g)t0​⋅(c/g)可能溢出故采用取模运算避免先分别对t 0 和 c / g t_0 和 c/gt0​和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 modt((t0​modmod)×((c/g)modmod))modmod最后若结果为负加上 (mod) 使其非负实际取模后已保证0 ≤ t m o d 0 \le t mod0≤tmod。输出得到的 t 即为所需跳的次数。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;// 使用 long long 避免溢出// 扩展欧几里得求 a*x b*y gcd(a,b) 的一组整数解 (x,y)// 返回 gcd(a,b)保证非负llexgcd(ll a,ll b,llx,lly){if(b0){x1;y0;returna0?a:-a;// 确保 gcd 为正数}ll gexgcd(b,a%b,y,x);// 递归求解y-a/b*x;// 回溯更新 yreturng;}intmain(){ll x,y,m,n,L;cinxymnL;// 将系数化为模 L 下的非负剩余ll a((m-n)%LL)%L;// a (m-n) mod Lll c((y-x)%LL)%L;// c (y-x) mod L// 特殊情况a 0if(a0){if(c0)cout0endl;// 已在同一点elsecoutImpossibleendl;return0;}ll t0,k0;// 用于存储 exgcd 得到的特解ll gexgcd(a,L,t0,k0);// g gcd(a, L)// 无解条件c 不能被 g 整除if(c%g!0){coutImpossibleendl;return0;}ll modL/g;// 通解的周期// 计算 t t0 * (c/g) 对 mod 取模的最小非负数// 为避免乘法溢出分步取模ll t((t0%mod)*((c/g)%mod))%mod;// 调整到 [0, mod-1] 区间取模结果已在区间内但确保非负t(tmod)%mod;couttendl;return0;}功能分析本程序实现了“青蛙的约会”问题的求解主要功能模块如下输入处理读取五个整数 (x, y, m, n, L)均为 long long 类型。方程标准化将原方程( 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否则无解。扩展欧几里得求解通过递归函数exgcd计算gcd ⁡ ( a , L ) \gcd(a, L)gcd(a,L)及一组特解时间复杂度O ( log ⁡ L ) O(\log L)O(logL)。解的存在性判断检查 c 能否被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}tt0​⋅(c/g)(modL/g)得到最小非负整数解。通过两次取模运算避免乘法溢出t 0 t_0t0​和c / g c/gc/g均可能较大但取模后相乘仍在 long long 范围内。输出结果打印跳的次数或Impossible。复杂度分析时间复杂度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各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}