模板—数学—Exgcd
2024-09-07 17:47:27
模板—数学—Exgcd
Code:
#include <cstdio>
#include <algorithm>
using namespace std;
int ex_gcd(int a,int b,int &x,int &y)
{
if(!b) {x=1,y=0;return a;}
int gcd=ex_gcd(b,a%b,x,y),tmp=x;
x=y,y=tmp-a/b*y; return gcd;
}
int a,b,c,gcd,x1,y1;
int main()
{
scanf("%d%d%d",&a,&b,&c),gcd=ex_gcd(a,b,x1,y1);
if(c%gcd) {printf("-1\n");return 0;}
x1*=c/gcd,y1*=c/gcd;
printf("x=%d+k*%d\n",x1,b/gcd);
printf("y=%d-k*%d\n",y1,a/gcd);
}
最新文章
- Windows下FFmpeg各版本库文件下载
- 【SQL语句】 - Ctrl+3 查询表属性的存储过程
- vlc播放yuv文件
- ftp客户端命令使用简记
- 漫谈刑事辩护 z
- udt nat traverse
- [转载][jQuery] Cannot read property ‘msie’ of undefined错误的解决方法
- 解析一下rtmp协议比较难懂的地方
- 1.Hibernate框架核心组件 (转自冯岩)
- UVa 10299 - Relatives
- Spring源码情操陶冶-AbstractApplicationContext
- 从头开始基于Maven搭建SpringMVC+Mybatis项目(2)
- JavaScript反调试技巧
- 转发:已知rsa的模数和指数 生成pem公钥文件
- H5 65-清除浮动方式一
- C# Note26: [MethodImpl(MethodImplOptions.Synchronized)]与lock机制
- Html table、thead、tr、th、td 标签
- react img 被自动转成base64,无法根据当前路径来动态改变值的解决办法
- ROS 进阶学习笔记(13) - Combine Subscriber and Publisher in Python, ROS
- XCode - 无法对iPhone真机调试的解决方法!