題目 2529:
信息學(xué)奧賽一本通T1632-NOIP2012-同余方程
時間限制: 2s
內(nèi)存限制: 192MB 提交: 51 解決: 23
題目描述
求關(guān)于 x 的同余方程 ax≡1(mod b) 的最小正整數(shù)解。
輸入格式
輸入只有一行，包含兩個正整數(shù) a,b，用一個空格隔開。
輸出格式
輸出只有一行，包含一個正整數(shù) x0 ，即最小正整數(shù)解。輸入數(shù)據(jù)保證一定有解。
提示
數(shù)據(jù)范圍與提示
對于 40% 的數(shù)據(jù)，有 2≤b≤1000；
對于 60% 的數(shù)據(jù)，有 2≤b≤50000000；
對于 100% 的數(shù)據(jù)，有 2≤a,b≤2000000000。