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

本文共 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

你可能感兴趣的文章
springBoot2.x设置quartz的overwriteExistingJobs参数
查看>>
VMware中通过克隆的Centos7,网卡突然没了
查看>>
学习笔记 DNS 子域授权 view
查看>>
stat函数
查看>>
在MyEclipse中部署项目到Tomcat服务器
查看>>
Kendo UI常用示例汇总(二十二)
查看>>
lnmp+coreseek实现站内全文检索(安装篇)
查看>>
六月技术指标和个人指标
查看>>
我的友情链接
查看>>
dojo layout
查看>>
初探 ELK - 每天5分钟玩转 Docker 容器技术(89)
查看>>
c#通过创建Windows服务启动程序
查看>>
系统架构设计指南
查看>>
我的友情链接
查看>>
Jquery Ajax方法传值到action
查看>>
亚马逊图书推荐--我感兴趣的
查看>>
Xmanager连接Centos6.3的远程桌面
查看>>
Office365:客户端升级后无法启动Microsoft Outlook
查看>>
我的友情链接
查看>>
在eclipse中查看Android源代码
查看>>