Discrete Logarithm Problems

题目描述

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

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

输入格式

输入按下列格式从标准输入给出： $N$ $P$ $A_1$ $\ldots$ $A_N$

输出格式

输出答案。

3 13
2 3 5

5

5 2
1 1 1 1 1

25

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

63

提示

$2 \leq N \leq 2 \times 10^5$ 1 \leq A_i < P $2 \leq P \leq 10^{13}$ $P$ 是素数。 所有输入值均为整数。有五对满足条件：$(1,1),(1,2),(1,3),(2,2),(3,3)$。 例如，对这一对 $(1,3)$，如果取 $k=9$，则 $A_1^9 = 512 \equiv 5 = A_3 \mod 13$。

标签: AtCoder|abc335G

来源

AtCoder|abc335G