← 返回题目列表

AtCoder · pakencamp_2021_day2_p

P. A的k次方等于k

中文机器翻译题面 查看原题

配点 : 800 点

問題文

T 案例的以下问题。 给出了

正整数 A,M 。 对于 A^k \equiv k \pmod M 的非负整数 查找 k\ (k < M \times \varphi (M)) 的数量 (ans ),满足条件 k 该值应乘以 \min(ans,1000) 请构建一个。

但是, 运算前设定中包含的 \varphi(M) 是 您也可以写欧拉 phi 函数 代表。

制約

  • 1 \le T \le 100
  • 1 \leq A,M \leq 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个案例均按以下格式给出。 打印

A M

出力

2T 行。 2i-1 减去 2i 行中, \mathrm{case}_i 的答案。

对于每种情况,它都在问题陈述的第一行中定义。 ans 下一行用空格分隔满足条件 k 该值应乘以 \min(ans,1000) 。

但是,输出 k 必须全部不同。


入力例 1

1
2 4

出力例 1

1
4

2^4\equiv 4 \pmod 4 。

原案: 海龟0123__