QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+1]

# 7978. 积性函数

Statistics

给定正整数 n,P 和长为 n 的数列 a1n,判断是否存在积性函数 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 个测试点。