当前位置: 首页 > news >正文

洛谷题单指南-进阶数论-P1516 青蛙的约会

原题链接:https://www.luogu.com.cn/problem/P1516

题意解读:长L的环形数轴,初始A在x坐标、一次跳m米,B在y坐标、一次跳n米,问最少跳几次AB相遇。

解题思路:

1、欧几里得算法

欧几里得算法(Euclidean Algorithm),又称辗转相除法,是数学中用于求解两个正整数最大公约数(Greatest Common Divisor, GCD) 的经典算法。其核心优势在于通过 “不断用较大数除以较小数,替换原数对为‘除数’和‘余数’” 的迭代过程,快速缩小数值规模,最终得到最大公约数。

欧几里得算法的可用递归描述为:对任意非负整数a和任意整数b,gcd(a,b) = gcd(b, a mod b)

证明:

设d|a且d|b,设a = bq + r,r = a mod b,r = a - bq则有d|r,即d | a mod b,因此a、b的约数也是b、a mod b的约数;

设d|b且d|a mod b,由a = bq + a mod b则有d|a,因此b、a mod b的约数也是a、b的约数;

综上,a,b和b,a mod b的约数相同,则最大公约数也一样,因此gcd(a,b) = gcd(b, a mod b)

代码:

int gcd(int a, int b)
{return b == 0 ? a : gcd(b, a % b);
}

2、扩展欧几里得算法

扩展欧几里得算法(Extended Euclidean Algorithm)是欧几里得算法(辗转相除法)的延伸,其核心价值不仅在于计算两个整数的最大公约数(gcd),更在于能找到满足裴蜀定理的一组整数解 —— 即对任意整数 ab,存在整数 xy 使得 ax + by = gcd(a, b)

其过程为:

设𝑎𝑥1 +𝑏𝑦1 = gcd(𝑎,𝑏),𝑏𝑥2 +(𝑎 mod 𝑏)𝑦2 = gcd(𝑏,𝑎 mod 𝑏)

由欧几里得定理可知:gcd(𝑎,𝑏) = gcd(𝑏,𝑎 mod 𝑏)

所以 𝑎𝑥1 +𝑏𝑦1 = 𝑏𝑥2 + (𝑎 mod 𝑏)𝑦2

又因为 𝑎 mod 𝑏 = 𝑎 − (⌊𝑎/𝑏⌋ ×𝑏)

所以 𝑎𝑥1 +𝑏𝑦1 = 𝑏𝑥2 +(𝑎 −(⌊𝑎/𝑏⌋ × 𝑏))𝑦2

𝑎𝑥1 +𝑏𝑦1 = 𝑎𝑦2 +𝑏𝑥2 −⌊𝑎/𝑏⌋ × 𝑏𝑦2 =𝑎𝑦2 + 𝑏(𝑥2 −⌊𝑎/𝑏⌋𝑦2)

所以 𝑥1 =𝑦2, 𝑦1 = 𝑥2 −⌊𝑎/𝑏⌋𝑦2

在递归过程中,x1,y1是上一层的x、y,x2、y2是下一层的x、y,当a mod b ==0时,此时的b即最大公约数,那么bx+0y=b,因此x=1 y=0是递归出口。

代码:

int exgcd(int a, int b, int &x, int &y)
{if(b == 0){x = 1;y = 0;return a;}int d = exgcd(b, a % b, y, x); //递归时上一层的x1=下一层的y2,上一层的y1 = 下一层的x2y -= a / b * x; //此时x1是下一层的y2,y1是下一层的x2,这句话的意思就是y1 = x2 - a / b * y2return d;
}

3、二元一次不定方程的通解

对于a、b是正整数,ax + by = c有解的条件是d | c,其中d = gcd(a, b),通过扩展欧几里得算法可以求得ax + by = d的解,设为x0,y0

那么ax + bx = c一个特解就是x1 = x0 * c / d, y1 = y0 * c / d

设k为任意整数,则ax + bx = c的通解可以表示为:x = x1 + (b / d) * k,y = y1 - (a / d) * k

要解x的最小正整数解,用(x1 % (b/d) + (b/d)) % (b/d)即可。

3、问题分析

经过时间t之后,A所在的位置变成(mt + x) % L,B所在位置变成(nt + y) % L

A、B要相遇,必须满足(mt + x) % L = (nt + y) % L,用同余表示即mt + x ≡ nt + y (mod L),

令设整数s,有mt + x + Ls = nt + y

进而(m - n)t + Ls = y - x

另a = |m - n|, b = L, c = ((y - x)% L + L) % L

求方程at + bs = c中t的最小正整数解即可

扩展欧几里得算法即可解决。

100分代码:

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
LL x, y, m, n, L;LL exgcd(LL a, LL b, LL &x, LL &y)
{if(b == 0){x = 1, y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main()
{cin >> x >> y >> m >> n >> L;LL a = abs(m - n), b = L, c = (m > n ? 1 : -1) * (y - x);LL s, t;LL d = exgcd(a, b, t, s);if(c % d){cout << "Impossible";return 0;}t *= (c / d);cout << (t % (b / d) + (b / d)) % (b / d);return 0;
}

 

http://www.hskmm.com/?act=detail&tid=13548

相关文章:

  • electron中的几个概念
  • 实用指南:告别IP被封!分布式爬虫的“隐身”与“分身”术
  • 从 “盲调” 到 “精准优化”:SQL Server 表统计信息实战指南
  • 别的摄像机都能国标GB28181注册上,就这台海康摄像机注册不上来,国标配置都反复检查没问题
  • 保护眼睛小程序
  • CSP-2025游寄
  • [::-1]的用法
  • 003_for循环操作列表和元组
  • linux 文件传输命令
  • 新手也能轻松上手!midas Gen 2019 安装详细图解
  • Redis AOF原理
  • 001_string操作
  • hbase 面试题
  • ANSYS Electronics 2025 R1 安装与使用全流程图文教程
  • mall项目学习笔记
  • 实用指南:通义DeepResearch论文六连发全面解读
  • glTF/glb:现在和未来
  • 存储多边形网格的文件格式:OBJ、FBX、RenderMan、glTF、USD 等。
  • 安防监控中常见的报警类型有哪些?国标GB28181平台EasyGBS的报警能力解析
  • Notepad++8.6免费版下载及安装教程(附安装包)2025最新整理
  • VTable-Sheet:重新定义Web电子表格的开源解决方案
  • Coolmuster Android Assistant:Windows架构下的Android设备管理专家
  • 负载均衡+Tomcat集群+MySQL主从 实验
  • mysql表新增字段,基本语法
  • 2025年运营商数据分类分级最佳实践、案例与方案
  • 微波雷达模块WT4101重新定义饮水机茶吧机等智能家居
  • 硝基甲苯之魇
  • day14-Trae之一键换脸APP开发04
  • Linux服务器单网卡如何配置多个的IP地址?
  • 面试常问问题——索引是不是越多越好