给定整数 KKK 和质数 mmm,求最小的正整数 NNN,使得 11⋯1 11\cdots111⋯1(NNN 个 111)≡K(modm)\equiv K \pmod m≡K(modm)。
说人话:就是 111⋯1111 mod m=K111\cdots 1111 \bmod m = K111⋯1111modm=K。
第一行两个整数,分别表示 KKK 和 mmm。
一个整数,表示符合条件最小的 NNN。
9 17
3
30%30\%30% 的数据保证 m≤106m\leq 10^6m≤106。
60%60\%60% 的数据保证 m≤5×107m\leq 5\times 10^7m≤5×107。
100%100\%100% 的数据保证 6≤m≤10116\leq m\leq 10^{11}6≤m≤1011,0<K<m0< K< m0<K<m,保证 mmm 是质数。
使用您的 Genisis Online Judge 通用账户