G - Discrete Logarithm Problems Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 個の整数 A_1,\ldots,A_N と素数 P が与えられます。 次の条件をともに満たす整数の組 (i,j) の個数を求めてください。

  • 1 \leq i,j \leq N
  • ある正整数 k が存在し、A_i^k \equiv A_j \bmod 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

(1,1),(1,2),(1,3),(2,2),(3,3) の 5 組が条件を満たします。

例えば (1,3) については、k=9 とすると A_1^9 = 512 \equiv 5 = A_3 \bmod 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

Score : 600 points

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