#PQJ934x4063. QOJ 934_4063

    ID: 3073 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2022倍增枚举

QOJ 934_4063

2022 年陕西省NOI 省队选拔赛试题 倍增(double) 倍增(double) 【题目描述】 小Z 是一个喜欢编程的女孩子。 这天,她在做一道编程题的时候偶然发现了一个神奇的整数142857。 142857 × 2 = 285714,而285714 的所有数位恰好是142857 的一个排列。 她很好奇,有没有更大的满足这种性质的整数。 她写了一个搜索的程序,发现了一些更大的有趣的数: 26835741 × 2 = 53671482 0987312654 × 2 = 1974625308 . . . 她不满足于解决十进制下这样的问题,于是她想知道,是否在B 进制下存在一个n 位正 整数x,满足2x 的所有数位在B 进制下是n 的所有数位的一个排列。 由于她讨厌数字0,因此她还要求对于任意1 ≤i ≤n,x 和2x 在B 进制下的第i 位不能 同时为0。 【输入格式】 从文件double.in 读入数据。 输入包含多组数据。 输入的第一行是一个正整数T,表示数据组数。 接下来T 行,第i 行包含两个正整数n 和B,表示第i 组数据。 【输出格式】 输出到文件double.out 中。 对于每组数据,输出一行。 若本组数据有解,按照从高位到低位的顺序输出n 个非负整数,表示你找到的答案在B 进 制下的值。 否则只需要输出一个数−1。 【样例输入1】 见选手目录下的double/double1.in。 3 6 10 3 3 6 7 第8 页,共13 页

2022 年陕西省NOI 省队选拔赛试题 倍增(double) 【样例输出1】 见选手目录下的double/double1.ans。 1 4 2 8 5 7 ‐1 0 3 5 3 1 6 【样例解释1】 第一组数据的解释参见【题目描述】。 对于第二组数据,可以通过枚举所有的n 位B 进制数说明一定不能找到这样的正整数。 对于第三组数据,2x 的7 进制表示为103635(7),因此这是一个满足题意的答案。 注意此样例的答案文件仅表明了一种可能的合法答案,不表明答案文件恰好对应标准程序 的输出。 【样例2】 见选手目录下的double/double2.in 和double/double2.ans。 本组数据满足测试点3 的限制。 注意此样例的答案文件仅表明了一种可能的合法答案,不表明答案文件恰好对应标准程序 的输出。 【样例3】 见选手目录下的double/double3.in 和double/double3.ans。 本组数据满足测试点17 的限制。 注意此样例的答案文件仅表明了一种可能的合法答案,不表明答案文件恰好对应标准程序 的输出。 【提示】 由于答案可能不唯一,我们下发了校验器checker.cpp 和库文件testlib.h。 可以使用以下命令编译checker.cpp: g++ ‐o checker checker.cpp ‐O2 ‐std=c++14 编译得到可执行文件checker 后,你可以使用以下方式测试你的答案: checker :利用选手目录下的double*.ans 可以用来检 验你的答案在样例测试点double*.in 的正确性。 checker :会检查你对这组数据的所有.有.解.输.出是否符合 题目要求。注意以此种方式测试的时候,输出无解总会被报告为合法。 .请.选.手.注.意.多.组.数.据.之.间.的.清.空.问.题。 第9 页,共13 页

2022 年陕西省NOI 省队选拔赛试题 倍增(double) 【数据规模与约定】 对于全部数据,1 ≤T ≤104,2 ≤∑B ≤2 × 105,1 ≤∑n ≤2 × 105,n ≥1,B ≥2。 具体的数据规模与约定见下表。 测试点编号 n B T 特殊约定 1 ≤8 ≤8 ≤10 无 2 ≤104 3 ≤2 × 105 ≤10 4 ≤104 5 6 ≤15 ≤15 ≤100 7 ≤40 ≤40 8 ≤100 ≤100 9 ≤300 ≤300 10 ≤1000 ≤1000 11 ≤3000 ≤3000 12 ≤15000 ≤15000 13 ≤50000 ≤50000 14 ≤2 × 105 ≤2 × 105 15 ≤200 ≤200 ≤104 n ≥100 16 ≤5000 ≤5000 17 ≤2 × 105 ≤2 × 105 18 ≤300 ≤300 B = 3k −1, k 为正整数 19 ≤2 × 105 ≤2 × 105 20 ≤300 ≤300 B = 3k, k 为正整数 21 ≤2 × 105 ≤2 × 105 22 ≤100 ≤100 无 23 ≤5000 ≤5000 24 ≤2 × 105 ≤2 × 105 25 第10 页,共13 页