#P1082. [NOIP2012 提高组] 同余方程

    ID: 665 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学2012NOIp 提高组扩展欧几里德扩欧

[NOIP2012 提高组] 同余方程

题目描述

求关于 x x 的同余方程 ax1(modb) a x \equiv 1 \pmod {b} 的最小正整数解。

输入格式

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

输出格式

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

3 10
7

提示

数据规模与约定

  • 对于 4040% 的数据,2b1,0002 ≤b≤ 1,000
  • 对于 6060% 的数据,2b50,000,0002 ≤b≤ 50,000,000
  • 对于 100100% 的数据,2a,b2,000,000,0002 ≤a, b≤ 2,000,000,000