Description

求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。

Input

输入文件为mod.in。

输入只有一行，包含两个正整数 a, b，用一个空格隔开。

Output

输出文件为mod.out。

输出只有一行，包含一个正整数 x ，即最小正整数解。输入数据保

证一定有解。

Sample Input

3 10

Sample Output

7

Data Constraint

Hint

对于40%的数据，2 ≤b≤ 1,000；

对于60%的数据，2 ≤b≤ 50,000,000；

对于100%的数据，2 ≤a, b≤ 2,000,000,000。

题解：

观察方程可得a与b一定互素，原式可化为 ax-kb=gcd(a,b)，所以用扩展欧几里得算法求出x最小正整数值即可。

最新文章

1. Linux之date
2. Android 第三方应用接入微信平台（1）
3. Python定时调度--多任务同一时间开始跑 scheduler.enterabs
4. OC：方法
5. 点(Dot)与像素(Pixel)的区别
6. 动网论坛password暴力破解程序代码
7. wamp5 忘记mysql root密码 重置方法
8. 简单学C——第一天
9. Noip 2014酱油记+简要题解
10. 关于出现Specified VM install not found: type Standard VM, name jdk1.5.0_04问题的解决办法
11. H5 54-清空默认边距
12. sqlldr的用法 (这个最完整)
13. strcpy函数解析
14. 公众号第三方平台开发 教程六 代公众号使用JS SDK说明
15. supervisor的command执行两条命令
16. Linux查看GPU信息和使用情况
17. Windows 2008 server R2安装.NET Framework4时提示“灾难性故障”
18. 纯C++binder服务和客户端实例
19. [OS] CPU调度
20. 基于c语言中调试工具的用法汇总(不包含gdb)【转】

热门文章

1. mysql类型转换函数convert与cast的用法,及SQL server的区别
2. Nginx---配置系统（自己总结）
3. Java自定义注解Annotation的使用
4. Express post请求无法解析参数的原因
5. Mongodb导入本地数据(.dat)到仓库(window)
6. linux IPC的PIPE
7. php 空格,换行,跳格使用说明
8. Sql生成 Insert 语句
9. CUDA编程入门笔记
10. 区分slice,splice,split