P15655 [ICPC 2025 Jakarta R] Nihilation

给定一个由 $N$ 个正整数组成的数组 $A = [A_1, A_2, \ldots, A_N]$。 在一次操作中，你可以选择整数 $m$ 和 $k$，满足 $1 \leq k < m \leq 10^9$，并对所有 $1 \leq i \leq N$ 将 $A_i$ 设置为 $(A_i \times k) \bmod m$。 问最少需要多少次操作才能使所有 $A_i$ 都变为 $0$？ 输出任意一种可行的操作序列。可以证明，总是有可能使所有 $A_i$ 变为 $0$。

输入以整数 $N$（$1 \le N \le 100\,000$）开始。下一行包含 $N$ 个整数 $A_i$（$1 \le A_i \le 10^9$），表示给定的数组 $A$。

第一行输出所需的最少操作次数 $q$。 接下来的 $q$ 行，每行输出两个整数 $m$ 和 $k$，表示使所有 $A_i$ 变为 $0$ 的操作序列中的一次操作。 如果存在多个满足条件的序列，输出其中任意一个即可。

**样例 1 解释：** 以下描述了样例输出中的操作序列。 - $A_i := (A_i \times 6) \bmod 12 \implies A = [0, 6, 0, 0, 6]$ - $A_i := (A_i \times 2) \bmod 3 \implies A = [0, 0, 0, 0, 0]$ 可以证明，不存在长度为 $1$ 的操作序列能使所有 $A_i$ 变为 $0$。 翻译由 DeepSeek V3.2 完成