/ Vijos / 题库 /

平方和的狂想

平方和的狂想

背景

这是最后一题了。

描述

给定一个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\))))。

信息

ID
1564
难度
9
分类
数论 点击显示
标签
递交数
301
已通过
23
通过率
8%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

zgx第一次模拟赛