P1516 青蛙的约会
2022/7/31 23:39:32
本文主要是介绍P1516 青蛙的约会,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目传送门
思路
因为两个青蛙同时跳到同一个点上才算碰面,设 $ t $ 为跳的次数, $ p $ 为两个青蛙跳的圈数之差,有如下式子:
\[(x+m \times t ) - ( y+n \times t ) = p \times L \]整理得:
\[(n-m) \times t + L \times p = x - y \]首先,要判断 $ \gcd ( n-m , L ) \nmid x-y $ 的情况。
然后,直接套拓展欧几里得算法,求出 $ (n-m) \times t + L \times p = \gcd ( n-m , L ) $ 一组解 $ t_0 \text{ , } p_0 \text{ , } gcd= \gcd ( n-m , L ) $ 。
特解:求 $ x $ 的最小正整数解,即 $ t = b / \gcd(a,b) \text{ , } x= ( x \bmod t + t ) \bmod t $
带入特解(本题求的是 $ t $ 的最小解),求出 $ (n-m) \times t + L \times p = \gcd ( n-m , L ) $ 中 $ t_0 $ 的最小解 $ t' $
\[t'= ( t_0 \bmod \dfrac{L}{gcd} + \dfrac{L}{gcd} ) \bmod \dfrac{L}{gcd} \]有
\[t = t' \times \dfrac{x - y}{gcd} \]所以
\[t=(\dfrac{x - y}{gcd} \times t_0 \bmod \dfrac{L}{gcd} + \dfrac{L}{gcd} ) \bmod \dfrac{L}{gcd} \]$ Code $
#define int long long signed main() { int x,y,m,n,l; int X,Y,gcd; cin>>x>>y>>m>>n>>l; int A=x-y,B=n-m; if(B<0)//注意取反!!! { B=-B; A=-A; } if(A%(gcd=exgcd(B,l,X,Y))!=0) cout<<"Impossible"<<endl; else cout<<( A/gcd * X % (l/gcd) + (l/gcd) ) % (l/gcd)<<endl; }
这篇关于P1516 青蛙的约会的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解