给定正整数 n,P 和长为 n 的数列 a1⋯n,判断是否存在积性函数 f(x) 同时满足:
- f(x) 的定义域和陪域均为正整数集。
- f(x) 在其定义域上非严格单调递增。
- ∀x∈[1,n],f(x)mod。
输入格式
本题有多组测试数据。
第一行两个正整数 T,ID ,分别表示数据组数和当前测试点所在的测试包编号。特别地,样例中 ID=0 。
接下来依次输入每组测试数据,对于每组测试数据:
第一行两个正整数 n,P ,意义如题。
第二行 n 个非负整数,第 i 个表示 a_i ,意义如题。
请注意,本题部分测试点读入量较大,故下发了附加文件中的 fastread.cpp
作为快速读入模板。
使用时只需将模板粘贴至代码中,调用 read()
时会从标准输入流中读入一个整数并返回,切勿将其与其它输入方式混用。保证标准算法的读入部分使用此模板实现。
若你仍然不理解如何使用此模板,可以查看附加文件中的 sample.cpp
,其中给出了一种示例实现,补全此代码即可。
输出格式
对于每组测试数据输出一行,若存在合法的 f(x) 则输出 YES
,否则输出 NO
。
请注意需要全部使用半角英文大写字母。
样例一
样例一输入
3 0 3 5 1 4 4 4 2023 1 2 2 2 5 2023 1 2 10 11 12
样例一输出
YES NO NO
样例一解释
本测试点包含三组测试数据。
对于第一组测试数据,取 f(x)=x^2 ,可以验证 f(x) 是合法的非严格单调递增的积性函数,符合题意。同时 f(1)\bmod 5={\color{red}1},f(2)\bmod 5={\color{red}4},f(3)\bmod 5 = 9\bmod 5={\color{red}4} 符合要求。
对于第二组测试数据,可以证明不存在合法的 f(x) 。比如,若 f(1)=1,f(2)=f(3)=f(4)=2 ,则可以得到 f(6)=f(12)=4 ,故 f(7)=f(10)=4,f(5)=2 ,于是 {\color{red}f(15)}=f(3)f(5)=4\ {\color{red}<f(14)}=f(2)f(7)=8 ,这构成了矛盾。
对于第三组测试数据,同样可以证明不存在合法的 f(x) 。比如,若 f(1)=1,f(2)=2,f(3)=10,f(4)=11,f(5)=12 ,则可以证明 f(6)=20\le f(7)\le f(10)=24 ,而 f(12)=110,f(14)\le 24\times 2=48,{\color{red}f(14)<f(12)} ,矛盾。
限于篇幅,无法于题面中对后两组测试数据中 f(x) 的不存在性给出完整证明。
数据规模与约定
对于 100\% 的数据, 1\leq T\leq 20,1\le n<P\le 5\times 10^6,0\le a_i<P 。
保证每个数据点中的 \sum n,\sum P\le 10^7 。
本题使用捆绑测试,且评测时会按照各测试包特殊限制的逻辑关系绑定依赖。
各测试包的分值和特殊限制如下:
测试包编号 | n,P\le | \sum n,\sum P\le | 保证 P 是质数 | 特殊性质 | 分值 |
---|---|---|---|---|---|
1 | 10^3 | 2\times 10^4 | 否 | a_1=0 | 2 |
2 | 10^3 | 2\times 10^4 | 否 | \forall i\in [1,n], a_i=1 | 3 |
3 | 10^3 | 2\times 10^4 | 否 | D | 4 |
4 | 10 | 50 | 是 | A | 12 |
5 | 10^3 | 2\times 10^4 | 是 | A | 13 |
6 | 10^3 | 2\times 10^4 | 是 | B | 7 |
7 | 3\times 10^5 | 6\times 10^5 | 是 | B | 5 |
8 | 10^3 | 2\times 10^4 | 是 | C | 14 |
9 | 3\times 10^5 | 6\times 10^5 | 是 | n=P-1 | 9 |
10 | 3\times 10^5 | 6\times 10^5 | 否 | P 是奇数 | 8 |
11 | 3\times 10^5 | 6\times 10^5 | 否 | 无特殊性质 | 15 |
12 | 10^6 | 2\times 10^6 | 否 | 无特殊性质 | 2 |
13 | 5\times 10^6 | 10^7 | 否 | 无特殊性质 | 6 |
特殊性质 A:保证如果存在合法的 f(x) ,则存在合法 f(x) 为严格单调递增的完全积性函数且满足 \forall x\le n,f(x)<P 。
特殊性质 B:保证如果存在合法的 f(x) ,则存在合法 f(x) 为严格单调递增的完全积性函数。
特殊性质 C:保证如果存在合法的 f(x) ,则存在合法 f(x) 严格单调递增。
特殊性质 D:保证 n=500 ,且每个 a_i 在 [0,P) 内独立地均匀随机生成。同时保证该测试包内恰有 3 个测试点。