AT_arc200_d.[ARC200D] |A + A|
省选/NOI-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定正整数 M,K。
请判断是否存在满足以下所有条件的正整数 N 和整数序列 A=(A1,A2,…,AN),如果存在,请给出其中一组解。
- 1≤N≤M。
- 0≤Ai<M(1≤i≤N)。
- 存在恰好 K 个整数 0≤k<M,对于每个这样的 k,存在一组下标对 (i,j),使得 k≡Ai+Aj(modM)。
给定 T 组测试用例,请分别输出每组的答案。
输入格式
输入按以下格式从标准输入读入。
T
case1
case2
⋮
caseT
每组测试用例格式如下:
M K
输出格式
请按顺序用换行分隔输出每组测试用例的答案。
对于每组测试用例,如果不存在满足条件的 N,A,输出 No。
否则,输出满足条件的 N 和 A,格式如下:
Yes N A1 A2 … AN
如果存在多组满足条件的 N 和 A,输出任意一组均可。
输入输出样例
输入#1
3 6 5 3 2 8 3
输出#1
Yes 3 3 1 4 No Yes 2 0 1
说明/提示
数据范围
- 1≤T≤2×105
- 1≤K≤M≤2×105
- 所有测试用例中 M 的总和不超过 2×105
- 输入的所有值均为整数
样例解释 1
对于第 1 个测试用例,若取 A=(3,1,4),则:
- k=0:取 (i,j)=(1,1),有 0≡3+3(mod6)。
- k=1:取 (i,j)=(1,3),有 1≡3+4(mod6)。
- k=2:取 (i,j)=(3,3),有 2≡4+4(mod6)。
- k=3:不存在满足条件的下标对 (i,j)。
- k=4:取 (i,j)=(1,2),有 4≡3+1(mod6)。
- k=5:取 (i,j)=(2,3),有 5≡1+4(mod6)。
因此,满足条件的 0≤k<6 恰好有 5 个。
由 ChatGPT 4.1 翻译
输入解题思路,AI测评打分。不知道怎么写?