平方和的狂想
测试数据来自 system/1564
背景
这是最后一题了。
描述
给定一个n,要求不定方程\(n^2=x^2+y^2\)的整数解个数。zgx做了这题后,认为太简单,于是就扩大了数据范围。为了能创造出足够大的数,我们令:
\(n=a_1^{a_2^{a_3^{\cdots ^{a_k}}}}\),
我们通过输入数列\(\{a_k\}\)这k个数来计算n。
例如,\(k=3\),\(a_1=5\),\(a_2=2\),\(a_3=3\),那么\(n=5^{2^3}=390625\),现在还是要求\(n^2=x^2+y^2\)的整数解个数,但由于整数解个数实在太多了!我们只要输出答案mod p的值即可。
格式
输入格式
第一行,两个数k,p。(\(k, p\le 10000\))
第二行,k个数。 每个数\(\le 10000\)。所有数都是质数,且都大于p。
输出格式
一行,\(n^2=x^2+y^2\)的整数解个数mod p的值。
样例1
样例输入1
2 3
5 7
样例输出1
0
样例2
样例输入2
1 5
7
样例输出2
4
提示
样例2说明:
4个解分别为:①x=7,y=0 ②x=-7,y=0 ③x=0,y=7 ④x=0,y=-7
数据规模:
对于20%的数据计算出来的\(n\le 10^8\)
对于100%的数据\(k,p\le 10000\),每个数\(a_i\le 10000\)
Hint:
\(n=a_1^{a_2^{a_3^{\cdots ^{a_k}}}}\),是从后向前算的,也就是n=\(a_1\)^(\(a_2\)^(\(a_3\)^(\(\cdots\)^\(a_k\))))。