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

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

 

对于$ax+by=c$,我们要求 $x$ 的最小正整数解,那么先求出 $ax+by=gcd(a,b)$ 中 $x$ 的解,那么在 $ax+by=gcd(a,b)$ 中 $x$ 的最小正整数解即可表示为:

$x=(x*k+b/gcd(a,b))$%$b/gcd(a,b)$

 

 

#include
#include
using namespace std;typedef long long ll;ll exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1,y=0; return a; } ll ans=exgcd(b,a%b,x,y); ll tmp=x; x=y,y=tmp-a/b*y; return ans;}int main(){ //freopen("in.txt","r",stdin); ll x,y,m,n,L; scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L); ll x1,y1; ll a=m-n,b=L,c=y-x; ll ans=exgcd(a,b,x1,y1); ll t=c/ans; if(c%ans!=0) { printf("Impossible\n");return 0; } x1*=t; ll mod=abs(b/ans); x1=((x1%mod)+mod)%mod; printf("%lld",x1); return 0;}

  

转载于:https://www.cnblogs.com/guangheli/p/9847080.html

你可能感兴趣的文章
可能是一场很 IN 的技术分享
查看>>
JavaEE--JSP指令
查看>>
杨建:网站加速--服务器编写篇(上)
查看>>
牛客网 完数VS盈数
查看>>
问题 1923: [蓝桥杯][算法提高VIP]学霸的迷宫 (BFS)
查看>>
60个高效、实用工具,快速创建各种Web App和移动App
查看>>
判断手机号归属运营商
查看>>
如何让JS的变量名变量化
查看>>
解决JQUERY $符号的冲突
查看>>
Codeforces #256 Div.2
查看>>
Node节点
查看>>
纯CSS写的对勾样式
查看>>
653. Two Sum IV - Input is a BST (Easy)
查看>>
华为机试题
查看>>
三国杀
查看>>
inode 详解
查看>>
Go语言基础之6--值类型和引用类型
查看>>
C#判断不同版本的Excel(转)
查看>>
【转载】游戏引擎发展史漫谈(资料整理)
查看>>
git的git bash使用
查看>>