‹ 上一题下一题 ›

j01806. 乘法阶未做

1000 ms 256 MB 测试点 10 J-34·初等数论 J·数学自拟题模运算与取余辗转相除法（GCD）

文件读写输入j01806.in输出j01806.out

题目描述

给互质的 $a, m$ ，求最小的正整数 $k$ 使 $a^{k} \equiv 1 (mod m)$ （ $a$ 在模 $m$ 下的乘法阶）。

输入格式

一行两个整数 $a, m$ （保证互质）。

输出格式

一行一个整数。

样例

输入

3 10

输出

数据范围

$1 \leq a < m \leq 1 0^{6}$
保证 $g cd (a, m) = 1$

输入

输出

答案