青蛙的约会
发布日期:2021-10-24 14:20:22 浏览次数:2 分类:技术文章

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

题目描述

求 x+m*t≡y+n*t (mod l)

题解

将上式

转换一下...

x-y≡(n-m)*t(mod l)

(n-m)*t+l*k=x-y...

然后用扩展欧几里得求...

因为我们用扩展欧几里得求出的是(n-m)*t+l*k=gcd(n-m,l)=(x-y)/k;(当 x-y % gcd(n-m,l) !=0时无解.

所以答案的 t=扩展欧几里得求出的t*(x-y)/gcd(n-m,l)

又因为要求是最小正整数解..

x=(x0%(b/gcd(a,b))+b/gcd(a,b))%(b/gcd(a,b))即为x的最小整数解。

至于为什么..

代码

#include
#include
#define LL long longusing namespace std;LL a,t,k,x,y,z,m,n,l,ans;LL gcd(LL x,LL y){ return y==0?x:gcd(y,x%y);}void exgcd(LL a,LL b,LL &x,LL &y){ if(!b){ x=1;y=0; return; } exgcd(b,a%b,x,y); z=x;x=y;y=z-a/b*y;}int main(){ scanf("%d%d%d%d%d",&x,&y,&m,&n,&l); a=m-n;k=y-x; t=gcd(a,l); if(k%t!=0){ printf("Impossible\n"); return 0; } exgcd(a,l,x,y); l=l/t;if(l<0)l=-l; x=x*k/t; printf("%d\n",(x%l+l)%l); return 0;}

 

转载于:https://www.cnblogs.com/zzyh/p/7327804.html

转载地址:https://blog.csdn.net/weixin_30791095/article/details/97944153 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:rest_framwork框架的简单使用
下一篇:freeRTOS中文实用教程3--中断管理之延迟中断处理

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月27日 22时37分39秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章