Houraisan Kaguya
Time Limit: 18000/15000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 71 Accepted Submission(s): 0
Problem Description
给定一个质数 $p$ 以及 $n$ 个 $[1,p)$ 范围内的整数 $a_1, a_2, \cdots, a_n$。
对于两个 $[1,p)$ 的整数 $a,b$，定义 $a$ 能被 $b$ 表示当且仅当存在一个非负整数 $x$，使得 $b^x \equiv a (\!\mod p)$，定义 $f(a,b)$ 为满足 $a^x$ 能被 $b$ 表示的最小的正整数 $x$。
求下列式子的值：
$$(\sum_{i=1}^{n}\sum_{j=1}^{n}f(a_i,a_j)\times f(a_j,a_i)) \mod p$$
对于两个 $[1,p)$ 的整数 $a,b$，定义 $a$ 能被 $b$ 表示当且仅当存在一个非负整数 $x$，使得 $b^x \equiv a (\!\mod p)$，定义 $f(a,b)$ 为满足 $a^x$ 能被 $b$ 表示的最小的正整数 $x$。
求下列式子的值：
$$(\sum_{i=1}^{n}\sum_{j=1}^{n}f(a_i,a_j)\times f(a_j,a_i)) \mod p$$
Input
输入第一行两个正整数 $n,p$。
接下来一行 $n$ 个 $[1,p)$ 范围内的正整数 $a_1, a_2, \cdots, a_n$。
$1 \le n \le 100000, 2 \le p \le 10^{18}, 1 \le a_i < p$
$p$ 是质数
样例解释
答案等于 $34 \mod 5 = 4$。
接下来一行 $n$ 个 $[1,p)$ 范围内的正整数 $a_1, a_2, \cdots, a_n$。
$1 \le n \le 100000, 2 \le p \le 10^{18}, 1 \le a_i < p$
$p$ 是质数
Hint
样例解释
答案等于 $34 \mod 5 = 4$。
Output
输出仅一行一个非负整数，表示答案。
Sample Input
4 5 1 2 3 4
Sample Output
4
Source
642ccpcQHD