模板—数学—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);
}

  

最新文章

  1. Windows下FFmpeg各版本库文件下载
  2. 【SQL语句】 - Ctrl+3 查询表属性的存储过程
  3. vlc播放yuv文件
  4. ftp客户端命令使用简记
  5. 漫谈刑事辩护 z
  6. udt nat traverse
  7. [转载][jQuery] Cannot read property ‘msie’ of undefined错误的解决方法
  8. 解析一下rtmp协议比较难懂的地方
  9. 1.Hibernate框架核心组件 (转自冯岩)
  10. UVa 10299 - Relatives
  11. Spring源码情操陶冶-AbstractApplicationContext
  12. 从头开始基于Maven搭建SpringMVC+Mybatis项目(2)
  13. JavaScript反调试技巧
  14. 转发:已知rsa的模数和指数 生成pem公钥文件
  15. H5 65-清除浮动方式一
  16. C# Note26: [MethodImpl(MethodImplOptions.Synchronized)]与lock机制
  17. Html table、thead、tr、th、td 标签
  18. react img 被自动转成base64,无法根据当前路径来动态改变值的解决办法
  19. ROS 进阶学习笔记(13) - Combine Subscriber and Publisher in Python, ROS
  20. XCode - 无法对iPhone真机调试的解决方法!

热门文章

  1. P2066 机器分配
  2. C# 获取ORACLE SYS.XMLTYPE &quot;遇到不支持的 Oracle 数据类型 USERDEFINED&quot;
  3. 【题解】SHOI2008仙人掌图
  4. 排查nginx、tomcat内存和服务器负载之后
  5. ar用法小记
  6. 从零开始学习MXnet(一)
  7. POJ2502:Subway(最短路)
  8. HDU3605:Escape(状态压缩+最大流)
  9. Google File System中文版
  10. 关于IE6的一些总结