pOJ-1061 exgcd求同余方程组
2024-09-28 22:44:14
就是求(m-n)*a+b*l=y-x,
类似于求解a*x+b*y=c,r=gcd(a,b),当c%r==0时有解,用exgcd求出a*x+b*y=gcd(a,b)的解,然后x*c/gcd(a,b)就是其中一个解,最后求最小正整数解,就是(x%b+b)%b,要求y的话,对应求解即可
#include<map> #include<set> #include<list> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; ; +,maxn=+,inf=0x3f3f3f3f; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll exgcd(ll a,ll b,ll &x,ll &y) { if(!b) { x=,y=; return a; } ll ans=exgcd(b,a%b,x,y); ll t=x;x=y;y=t-a/b*y; return ans; } int main() { ll x,y,n,m,l,a,b; scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l); if(m<n)swap(x,y),swap(m,n); ll r=gcd(m-n,l); )*puts("Impossible"); exgcd(m-n,l,a,b); a*=(y-x)/r; a=(a%l+l)%l; printf("%lld\n",a); ; } /******************** ********************/
最新文章
- javascript中的变量作用域以及变量提升
- SGIP、SMGP 长短信发送问题小结
- Windows - 杀死占用某个端口号的进程
- EmguCV 轮廓匹配
- 如何启动/停止/重启MySQL
- vim编辑器,管道,输入输出重定向
- 关于inf的问题
- [置顶] .net技术类面试、笔试题汇总1
- 【百度之星2014~初赛(第二轮)解题报告】Chess
- iOS开发- &;quot;duplicate symbol for architecture i386&;quot; 解决的方法
- C语言的变量的内存分配
- 把JavaScript代码改成ES6语法不完全指南
- 装饰模式(Decorator)
- CAD 二次开发 -- 自动加载开发的DLL
- Foundation框架 - 结构体
- 雷林鹏分享:jQuery EasyUI 数据网格 - 设置排序
- Netty客户端发送消息并同步获取结果
- AS安装过程中出现的错误
- Mysql修改字段类型,修改字段名
- Linux netstat
热门文章
- 3*0.1 == 0.3 将会返回什么?true 还是 false?
- numpy.random.random &; numpy.ndarray.astype &; numpy.arange
- 我的Android进阶之旅------>解决:Execution failed for task ':app:transformResourcesWithMergeJavaResForDebug'.
- django Form表单的使用
- asp.net Mvc Npoi 导出导入 excel
- Java IO流简单使用
- restful API(转自阮一峰)
- Nhibernate工具Profiler配置
- JavaScript:学习笔记(7)——VAR、LET、CONST三种变量声明的区别
- Unity 自定义编辑窗体之ScriptableWizard