#1818. 积性函数

    ID: 1818 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1456来源:qoj.ac数据:公开样例数论

积性函数

积性函数

题目描述

标题: 积性函数 - Problem - QOJ.ac

#7978. 积性函数

Statistics

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