Home => ProblemSet => [NOIP 2012 提高组] 同余方程
Problem2279--[NOIP 2012 提高组] 同余方程

2279: [NOIP 2012 提高组] 同余方程

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 2
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

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

Input

一行，包含两个整数 a,b，用一个空格隔开。

Output

一个整数 x0，即最小正整数解。输入数据保证一定有解。

Sample Input Copy 

3 10

Sample Output Copy 

7

HINT

  • 对于 40% 的数据，2≤b≤1,000；
  • 对于 60% 的数据，2≤b≤50,000,000；
  • 对于 100% 的数据，2≤a,b≤2,000,000,000。

Source/Category

逆元 算法 数论 NOIP 2012 复赛 提高组 第四题 
[ Submit ] [ Status ]