103356: [Atcoder]ABC335 G - Discrete Logarithm Problems

Problem Statement

You are given $N$ integers $A_1,\ldots,A_N$ and a prime number $P$. Find the number of pairs of integers $(i,j)$ that satisfy both of the following conditions:

• $1 \leq i,j \leq N$;
• There is a positive integer $k$ such that $A_i^k \equiv A_j \mod P$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i < P$
• $2 \leq P \leq 10^{13}$
• $P$ is prime.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $P$
$A_1$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

3 13
2 3 5

Sample Output 1

5

Five pairs satisfy the conditions: $(1,1),(1,2),(1,3),(2,2),(3,3)$.

For example, for the pair $(1,3)$, if we take $k=9$, then $A_1^9 = 512 \equiv 5 = A_3 \mod 13$.

Sample Input 2

5 2
1 1 1 1 1

Sample Output 2

25

Sample Input 3

10 9999999999971
141592653589 793238462643 383279502884 197169399375 105820974944 592307816406 286208998628 34825342117 67982148086 513282306647

Sample Output 3

63

问题描述

给你$N$个整数$A_1,\ldots,A_N$和一个素数$P$。找出满足以下两个条件的整数对$(i,j)$的数量：

• $1 \leq i,j \leq N$；
• 存在正整数$k$，使得$A_i^k \equiv A_j \mod P$。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i < P$
• $2 \leq P \leq 10^{13}$
• $P$是素数。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$N$ $P$
$A_1$ $\ldots$ $A_N$

输出

打印答案。

样例输入1

3 13
2 3 5

样例输出1

5

有5对满足条件：$(1,1),(1,2),(1,3),(2,2),(3,3)$。

例如，对于对$(1,3)$，如果我们取$k=9$，那么$A_1^9 = 512 \equiv 5 = A_3 \mod 13$。

样例输入2

5 2
1 1 1 1 1

样例输出2

25

样例输入3

10 9999999999971
141592653589 793238462643 383279502884 197169399375 105820974944 592307816406 286208998628 34825342117 67982148086 513282306647

样例输出3

63