poj2891 拓展欧几里得
2024-10-07 01:33:01
//Accepted 164 KB 16 ms //拓展欧几里得 //m=a1*x+b1 --(1) //m=a2*(-y)+b2 --(2) //->a1*x+a2*y=b2-b1 //由欧几里得算法可得上式的解 //由a*x+b*y=gcd(a,b) //可得a(x+b)+b(y-a)=gcd(a,b) //所以最小正整数解x=(x%b+b)%b; //现考虑由(1)(2)两式得到的解m //有x=m mod (a1*a2/gcd(a1,a2)) //m是最小正整数解,m+a1*a2/gcd(a1,a2)也是(1)(2)的解 #include <cstdio> #include <cstring> #include <iostream> using namespace std; __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y) { ) { x=; y=; return a; } __int64 r=extend_gcd(b,a%b,x,y); __int64 t=x; x=y; y=t-a/b*y; return r; } int main() { int n; while (scanf("%d",&n)!=EOF) {; __int64 a1,b1,a2,b2; __int64 x,y,c,d; scanf("%I64d%I64d",&a1,&b1); ;i<=n;i++) { scanf("%I64d%I64d",&a2,&b2); if (flag) continue; d=extend_gcd(a1,a2,x,y); c=b2-b1; if (c%d) { flag=; } else { __int64 p=a2/d; x=(c/d*x%p+p)%p; b1=a1*x+b1; a1=a1/d*a2; } } if (flag) printf("-1\n"); else printf("%I64d\n",b1); } ; }
最新文章
- Jquery 获得当前标签的名称和标签属性
- PHP 静态
- js_多个引号的用法
- BADI
- STL标准模板库介绍
- Hibernate的单向OneToMany、单向ManyToOne
- UVA 10896 Sending Email
- BufferedInputStream,FileInputStream,FileChannel实现文件拷贝
- sizeToFit的用法和用途
- BootStrap入门教程 (四)
- angular2 学习笔记 ( app initialize 初始化 )
- Android 字体适配方案
- UE3中的时间
- k8s Docker私有仓库认证
- linux 防火墙 iptables 目录
- JavaEE思维导图
- Appium -选择、操作元素3
- 获取当前操作的IFrame对象的方法
- 设置idealUI选中变量的颜色与同名称变量的颜色一致
- UVa 230 Borrowers(map和set)
热门文章
- Scroller 实现的弹性回弹的LinearLayout
- Java并发编程:并发容器之CopyOnWriteArrayList
- validate插件:验证密码没有空格 用户名是5-10位 至少包含数字和大小写字母中的两种字符
- nodeschool.io 2
- HTML5自学笔记[ 20 ]canvas绘图实例之绘制倒影
- C实现多线程
- python中字典dict的操作
- hdu-----(2807)The Shortest Path(矩阵+Floyd)
- 《Play for Java》学习笔记(七)数据类型解析——Body parser
- spring项目中使用定时任务