#1818. 积性函数
积性函数
积性函数
题目描述
标题: 积性函数 - Problem - QOJ.ac
#7978. 积性函数
The problem was used in the following contests:
给定正整数 n,P 和长为 n 的数列 a1⋯n,判断是否存在积性函数 f(x) 同时满足:
- f(x) 的定义域和陪域均为正整数集。
- f(x) 在其定义域上非严格单调递增。
- ∀x∈[1,n],f(x)modP=ax。
输入格式
本题有多组测试数据。
第一行两个正整数 T,ID,分别表示数据组数和当前测试点所在的测试包编号。特别地,样例中 ID=0。
接下来依次输入每组测试数据,对于每组测试数据:
第一行两个正整数 n,P,意义如题。
第二行 n 个非负整数,第 i 个表示 ai,意义如题。
请注意,本题部分测试点读入量较大,故下发了附加文件中的 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)=x2,可以验证 f(x) 是合法的非严格单调递增的积性函数,符合题意。同时 f(1)mod5=1,f(2)mod5=4,f(3)mod5=9mod5=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,于是 f(15)=f(3)f(5)=4 <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≤f(7)≤f(10)=24,而 f(12)=110,f(14)≤24×2=48,f(14)<f(12),矛盾。
限于篇幅,无法于题面中对后两组测试数据中 f(x) 的不存在性给出完整证明。
数据规模与约定
对于 100% 的数据,1≤T≤20,1≤n<P≤5×106,0≤ai<P。
保证每个数据点中的 ∑n,∑P≤107。
本题使用捆绑测试,且评测时会按照各测试包特殊限制的逻辑关系绑定依赖。
各测试包的分值和特殊限制如下:
测试包编号n,P≤∑n,∑P≤保证 P 是质数特殊性质分值11032×104否a1=0221032×104否∀i∈[1,n],ai=1331032×104否D441050是A1251032×104是A1361032×104是B773×1056×105是B581032×104是C1493×1056×105是n=P−19103×1056×105否P 是奇数8113×1056×105否无特殊性质15121062×106否无特殊性质2135×106107否无特殊性质6
特殊性质 A:保证如果存在合法的 f(x),则存在合法 f(x) 为严格单调递增的完全积性函数且满足 ∀x≤n,f(x)<P。
特殊性质 B:保证如果存在合法的 f(x),则存在合法 f(x) 为严格单调递增的完全积性函数。
特殊性质 C:保证如果存在合法的 f(x),则存在合法 f(x) 严格单调递增。
特殊性质 D:保证 n=500,且每个 ai 在 [0,P) 内独立地均匀随机生成。同时保证该测试包内恰有 3 个测试点。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 0
3 5
1 4 4
4 2023
1 2 2 2
5 2023
1 2 10 11 12
YES
NO
NO