AcWing算法提高课-5.6.2青蛙的约会

宣传一下 算法提高课整理

CSDN个人主页:更好的阅读体验

Start

原题链接
题目描述

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。

它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。

可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。

不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。

但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。

为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙 A A A 和青蛙 B B B,并且规定纬度线上东经 0 0 0 度处为原点,由东往西为正方向,单位长度 1 1 1 米,这样我们就得到了一条首尾相接的数轴。

设青蛙 A A A 的出发点坐标是 x x x,青蛙 B B B 的出发点坐标是 y y y

青蛙 A A A 一次能跳 m m m 米,青蛙 B B B 一次能跳 n n n 米,两只青蛙跳一次所花费的时间相同。

纬度线总长 L L L 米。

现在要你求出它们跳了几次以后才会碰面。

输入格式

输入只包括一行 5 5 5 个整数 x , y , m , n , L x,y,m,n,L xymnL

输出格式

输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行 Impossible

数据范围

x ≠ y < 2000000000 x \neq y < 2000000000 x=y<2000000000,
0 < m , n < 2000000000 0 < m,n < 2000000000 0<m,n<2000000000,
0 < L < 2100000000 0 < L < 2100000000 0<L<2100000000

输入样例:
1 2 3 4 5
输出样例:
4

思路

以下是简化过后的题目描述:

给定 a , b , m , n , L a, b, m, n,L a,b,m,n,L,求关于 x x x 的同余方程 ( m − n ) x ≡ b − a ( m o d L ) (m-n)x \equiv b-a\pmod L (mn)xba(modL) 的正整数解


根据扩展欧几里得算法,我们先求出方程 ( m − n ) x − L y = gcd ⁡ ( m − n , L ) (m-n)x-Ly=\gcd(m-n,L) (mn)xLy=gcd(mn,L) 的解 x 0 x_0 x0

根据裴蜀定理,只有当 gcd ⁡ ( m − n , L ) ∣ b − a \gcd(m-n,L)|b-a gcd(mn,L)ba 时,方程有整数解。

故:若不能整除则输出 Impossible

否则,根据余数的性质,方程 ( m − n ) x ≡ b − a ( m o d L ) (m-n)x \equiv b-a\pmod L (mn)xba(modL) 的可行解 x x x 为: x = x 0 × b − a gcd ⁡ ( m − n , L ) x=x_0\times \frac{b-a}{\gcd(m-n,L)} x=x0×gcd(mn,L)ba

通解为: x + k × L gcd ⁡ ( m − n , L ) ( k ∈ Z ) x+k\times\frac{L}{\gcd(m-n,L)}(k \in \mathbb{Z}) x+k×gcd(mn,L)L(kZ)

此时求出最小正整数解即为答案。

算法时间复杂度
AC Code

C + + \text{C}++ C++

#include <iostream>
#define int long longusing namespace std;int exgcd(int a, int b, int &x, int &y)
{if (!b){x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}signed main()
{int a, b, x, y, l, m, n;cin >> a >> b >> m >> n >> l;int d = exgcd(m - n, l, x, y);if ((b - a) % d) puts("Impossible");else{x *= (b - a) / d;int t = abs(l / d);cout << (x % t + t) % t << endl; // 正整数解}return 0;
}

228aa7bed3e021faf24cf8560d3e47bb.gif

最后,如果觉得对您有帮助的话,点个赞再走吧!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/161539.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数据库设计与前端框架

数据库设计与前端框架 学习目标&#xff1a; 理解多租户的数据库设计方案 熟练使用PowerDesigner构建数据库模型理解前端工程的基本架构和执行流程 完成前端工程企业模块开发 多租户SaaS平台的数据库方案 多租户是什么 多租户技术&#xff08;Multi-TenancyTechnology&a…

PCI设备与UIO驱动

随着网络的高速发展,对网络的性能要求也越来越高,DPDK框架是目前的一种加速网络IO的解决方案之一,也是最为流行的一套方案。DPDK通过bypass内核协议栈与内核驱动,将驱动的工作从内核态移至用户态,并利用polling mode的线程工作模式加速网络I/O使得网络IO性能出现大幅度的增…

xml文件报错 ORA-00907: 缺失右括号

原来的sql 更改之后 加一个select * from &#xff08;&#xff09;

一文理解登录鉴权(Cookie、Session、Jwt、CAS、SSO)

1 前言 登录鉴权是任何一个网站都无法绕开的部分&#xff0c;当系统要正式上线前都会要求接入统一登陆系统&#xff0c;一方面能够让网站只允许合法的用户访问&#xff0c;另一方面&#xff0c;当用户在网站上进行操作时也需要识别操作的用户&#xff0c;用作后期的操作审计。…

嵌入式开发学习之STM32F407点亮LED及J-Link下载(二)

嵌入式开发学习之STM32F407点亮LED及J-Link下载&#xff08;二&#xff09; 开发涉及工具控制端口配置端口的设定与确认端口配置方法实现点亮LED程序下载与仿真 有工程实例&#xff0c;链接在最底部。 开发涉及工具 开发环境&#xff08;IDE&#xff09;&#xff1a;IAR-ARM8…

力扣每日一题46:全排列

题目描述&#xff1a; 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2&#xff1a; …

Tuxera NTFS2024最新永久版下载和安装

要使用Tuxera NTFS for Mac&#xff0c;你需要先下载和安装Tuxera NTFS for Mac驱动器&#xff0c;然后按照以下步骤操作&#xff1a; 1、下载和安装Tuxera NTFS for Mac 免费下载Tuxera NTFS for Mac驱动器的最新版本。下载完成后&#xff0c;双击DMG文件并按照提示安装即可…

云计算:shell脚本

shell脚本&#xff0c;会极大减少重复性工作&#xff0c;缩短很大时间。 脚本每个人都可以不一样&#xff0c;只要实现就可以。 注意&#xff1a;要多思考&#xff0c;把思路锻炼好。以后就可以写各种程序。 shell语言 学完shell之后&#xff0c;对Linux理解更深刻&#xff…

IDEA 修改插件安装位置

不说假话&#xff0c;一定要看到最后&#xff0c;不然你以为我为什么要自己总结&#xff01;&#xff01;&#xff01; IDEA 修改插件安装位置 前言步骤 前言 IDEA 默认的配置文件均安装在C盘&#xff0c;使用时间长会生成很多文件&#xff0c;这些文件会占用挤兑C盘空间&…

如何使用前端模块化开发?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…

vue中引入jquery解决跨域问题

1、vue 工程文件 package.json 中 引入 “dependencies”: { “jquery”:“^2.2.4” }, 2、控制台执行命令&#xff0c;当前工程文件夹下 cnpm install 3、修改的vue文件中 加入 import $ from ‘jquery’ 4、调用 ajax请求 $.ajax({url:http://192.168.0.10:9099/strutsJspA…

Vue Router - 路由的使用、两种切换方式、两种传参方式、嵌套方式

目录 一、Vue Router 1.1、下载 1.2、基本使用 a&#xff09;引入 vue-router.js&#xff08;注意&#xff1a;要在 Vue.js 之后引入&#xff09;. b&#xff09;创建好路由规则 c&#xff09;注册到 Vue 实例中 d&#xff09;展示路由组件 1.3、切换路由的两种方式 1.…

会议OA小程序首页布局

目录 一. Flex布局介绍 1.1 什么是Flex布局 1.2 基本概念 1.3 Flex属性 二. 会议OA首页轮播图的实现 配置 Mock工具 swiper 效果展示 三. 会议OA首页会议信息布局 index.js index.wxml index.wxss 首页整体效果展示 一. Flex布局介绍 布局的传统解决方案&#x…

简单的对称加密

异或 异或算法的好处便是数A和数B异或后&#xff0c;把结果再和数A异或便可得到B&#xff0c;或者和数B异或可重新得到数据A。利用异或的这个特性可简单实现数据的加密和解密算法。 恺撒密码 恺撒密码的替换方法是通过排列明文和密文字母表&#xff0c;密文字母表示通过将明…

MATLAB | 对随机信号进行统计分析,绘制频次直方图、频率分布图,与理论概率密度进行比较

一、问题描述 对于一个随机信号&#xff0c;我们可以通过统计手段&#xff0c;得到其的频次分布图&#xff08;直方图&#xff09;&#xff0c;并由此计算出它的频率分布图。当观察次数区域无穷大时&#xff0c;频率分布图近似于概率密度函数。 下面我们以稳定分布的随机变量为…

互联网Java工程师面试题·Java 总结篇·第五弹

目录 47、Java 语言如何进行异常处理&#xff0c;关键字&#xff1a;throws、throw、try、catch、finally 分别如何使用&#xff1f; 48、运行时异常与受检异常有何异同&#xff1f; 49、列出一些你常见的运行时异常&#xff1f; 50、阐述 final、finally、finalize 的区别…

在 IDEA 中的各种调试技巧,轻松定位 Bug(超级全面)

在现在的开发中&#xff0c;我们经常采用Debug来追踪代码的运行流程&#xff0c;通常在程序运行过程中出现异常&#xff0c;启用Debug模式可以分析定位异常发生的位置&#xff0c;以及在运行过程中参数的变化。通常我们也可以启用Debug模式来跟踪代码的运行流程去学习三方框架的…

Orleans的成员管理和故障检测故障检测

Orleans的成员管理和故障检测故障检测 简介 Orleans框架是一个基于.NET平台的开源分布式系统框架&#xff0c;用于开发可扩展&#xff0c;高可用&#xff0c;高性能的云服务应用程序。它采用了Actor模型&#xff0c;将分布式系统中的各个节点抽象成为Actor&#xff0c;使得开…

蓝桥杯每日一题2023.10.17

迷宫 - 蓝桥云课 (lanqiao.cn) 题目描述 样例&#xff1a; 01010101001011001001010110010110100100001000101010 00001000100000101010010000100000001001100110100101 01111011010010001000001101001011100011000000010000 0100000000101010001101000010100000101010101100…

nginx正反向代理,负载均衡

Nginx 正向代理&#xff0c;反向代理 &#xff0c;负载均衡 Nginx有两种代理协议 七层代理&#xff08;http协议&#xff09; 四层代理&#xff08;tcp/udp流量转发&#xff09; 四层代理七层代理概念 四层代理 四层代理&#xff1a;基于tcp/ip协议层的转发代理方式&#…