#1485. 「一本通 6.4 例 2」同余方程
「一本通 6.4 例 2」同余方程
题目描述
求关于 x 的同余方程 ax≡1(mod b) 的最小正整数解。
输入
输入只有一行,包含两个正整数 a,b,用一个空格隔开。
输出
输出只有一行,包含一个正整数 x0 ,即最小正整数解。输入数据保证一定有解。
样例
3 10
7
提示
数据范围与提示
对于 的数据,有 ;
对于 的数据,有 ;
对于 的数据,有 。
求关于 x 的同余方程 ax≡1(mod b) 的最小正整数解。
输入只有一行,包含两个正整数 a,b,用一个空格隔开。
输出只有一行,包含一个正整数 x0 ,即最小正整数解。输入数据保证一定有解。
3 10
7
数据范围与提示
对于 40 的数据,有 2≤b≤1000;
对于 60 的数据,有 2≤b≤50000000;
对于 100 的数据,有 2≤a,b≤2000000000。