AT_arc200_d.[ARC200D] |A + A|

省选/NOI-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定正整数 M,KM,K。

请判断是否存在满足以下所有条件的正整数 NN 和整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N),如果存在,请给出其中一组解。

  • 1≤N≤M1\le N\le M。
  • 0≤Ai<M0\le A_i < M(1≤i≤N1\le i\le N)。
  • 存在恰好 KK 个整数 0≤k<M0\le k < M,对于每个这样的 kk,存在一组下标对 (i,j)(i,j),使得 k≡Ai+Aj(modM)k\equiv A_i+A_j\pmod M。

给定 TT 组测试用例,请分别输出每组的答案。

输入格式

输入按以下格式从标准输入读入。

TT
case1\text{case}_1
case2\text{case}_2
⋮\vdots
caseT\text{case}_T

每组测试用例格式如下:

M KM\ K

输出格式

请按顺序用换行分隔输出每组测试用例的答案。

对于每组测试用例,如果不存在满足条件的 N,AN,A,输出 No。

否则,输出满足条件的 NN 和 AA,格式如下:

Yes NN A1A_1 A2A_2 …\ldots ANA_N

如果存在多组满足条件的 NN 和 AA,输出任意一组均可。

输入输出样例

  • 输入#1

    3
    6 5
    3 2
    8 3

    输出#1

    Yes
    3
    3 1 4
    No
    Yes
    2
    0 1

说明/提示

数据范围

  • 1≤T≤2×1051\le T\le 2\times 10^5
  • 1≤K≤M≤2×1051\le K\le M\le 2\times 10^5
  • 所有测试用例中 MM 的总和不超过 2×1052\times 10^5
  • 输入的所有值均为整数

样例解释 1

对于第 11 个测试用例,若取 A=(3,1,4)A=(3,1,4),则:

  • k=0k=0:取 (i,j)=(1,1)(i,j)=(1,1),有 0≡3+3(mod6)0\equiv 3+3\pmod 6。
  • k=1k=1:取 (i,j)=(1,3)(i,j)=(1,3),有 1≡3+4(mod6)1\equiv 3+4\pmod 6。
  • k=2k=2:取 (i,j)=(3,3)(i,j)=(3,3),有 2≡4+4(mod6)2\equiv 4+4\pmod 6。
  • k=3k=3:不存在满足条件的下标对 (i,j)(i,j)。
  • k=4k=4:取 (i,j)=(1,2)(i,j)=(1,2),有 4≡3+1(mod6)4\equiv 3+1\pmod 6。
  • k=5k=5:取 (i,j)=(2,3)(i,j)=(2,3),有 5≡1+4(mod6)5\equiv 1+4\pmod 6。

因此,满足条件的 0≤k<60\le k<6 恰好有 55 个。

由 ChatGPT 4.1 翻译

输入解题思路,AI测评打分。不知道怎么写?

首页