4852: [NOIP2012 提高组] 同余方程

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：8 Solved：2

Description

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


Input

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


Output


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




Sample Input Copy 

3 10

Sample Output Copy 

7

HINT

数据规模与约定

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

Source/Category

SubmitSubmit RecordStatisticsShowOff!