#P13799. [tenka1 2017]ModularPowerEquation!!

    ID: 13000 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-扩展欧拉定理扩展 CRT欧拉函数试除法分解质因数扩展欧几里得算法快速幂

[tenka1 2017]ModularPowerEquation!!

题目描述

输入QQ (1≤Q≤100)(1\leq Q\leq 100)组A,MA,M $(0\leq A_i\leq 10^9, 1\leq M_i\leq 10^9(1\leq i\leq Q))$,求任意一个KK (1≤K≤2×1018)(1\leq K\leq 2\times 10^{18}),使得AK≡K (mod M)A^K\equiv K\ (mod\ M)

输入格式

Q Q

A1 A_1 M1 M_1

…\dots

AQ A_Q MQ M_Q

输出格式

第ii行输出第ii组的KK值,若没有合法的KK,则输出-1

输入输出样例 #1

输入 #1

4
2 4
3 8
9 6
10 7

输出 #1

4
11
9
2

输入输出样例 #2

输入 #2

3
177 168
2028 88772
123456789 987654321

输出 #2

7953
234831584
471523108231963269