博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
青蛙的约会(扩展欧几里得)
阅读量:6680 次
发布时间:2019-06-25

本文共 711 字,大约阅读时间需要 2 分钟。

#include
#include
#define ll long longusing namespace std;ll gcd(ll a,ll b,ll &x,ll &y){ if(!b){ x=1,y=0; return a; } int ret=gcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return ret;} int main(){ll x,y;ll a,b;ll m,n,l,X,Y;ll g; scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l); if(n-m<0)swap(m,n),swap(x,y); if((x-y)%(g=gcd(n-m,l,X,Y))!=0) printf("Impossible"); else printf("%lld",((x-y)/g*X%(l/g)+(l/g))%(l/g)); }

  有数学关系可得(m-n)x+(a-b)≡ 0(mod l)

  即 (m-n)x+l*y=(b-a)

  由扩展欧几里得得(m-n)x0+l*y0=gcd(a,b) ————两边同时乘(b-a)/gcd(a,b)!!!必须是整数&&(m-n>0)

  ->>(m-n)x0*(b-a)/gcd(a,b)+l*y0*(b-a)/gcd(a,b)=(b-a)

  则可以用扩展欧几里得求出x0,再乘(b-a)/gcd(a,b)

转载于:https://www.cnblogs.com/wspl98765/p/6883925.html

你可能感兴趣的文章
Logback中文文档(三):配置
查看>>
【java】【多线程】等待开启的多个线程都执行完成,再做事情,怎么实现
查看>>
java 判断String字符串是不是json数据
查看>>
psql: FATAL: role “postgres” does not exist
查看>>
新版剑指offer14 剪绳子
查看>>
Feign 请求拦截器和日志
查看>>
WPF内实现与串口发送数据和接收数据
查看>>
Ideal test 不执行main方法了
查看>>
kbengine_js_plugins
查看>>
ElasticSearch的各种服务的URL
查看>>
工厂模式之数据工厂
查看>>
IBM Java多线程 - 1. 线程基础
查看>>
关系数据库的末日是否已经来临(转载)
查看>>
Myeclipse中导入jar包的方法
查看>>
topcoder srm 715 div1 -23
查看>>
梯度下降(Gradient Descent)小结
查看>>
一起谈.NET技术,使用User Control做HTML生成
查看>>
谷歌启动搜索引擎新功能 网页Flash内容即时预览
查看>>
专访梭子鱼:以“立体交付”保障Web应用安全
查看>>
微软SQL Server 2012新特性Silverlight报表客户端 - Power View
查看>>