「WHOI-4」ggcd

Luogu

IDLGP8961

Time1000ms

Memory512MB

DifficultyP5

数论Special JudgeO2优化素数判断,质数,筛法中国剩余定理 CRT

**本题已新增一组样例，请注意查看。** 小 Y 给了你长度为 $n$ 的数组 $y$ 以及一个正整数 $m$，保证 $0\le y_i<m$，请你构造一个同样长为 $n$ 的数组 $x$，使得： 1. $x_i$ 在 `__int128` 范围内； 2. $x_i\bmod m=y_i$； 3. $\gcd(|x_1|,\cdots,|x_n|)\bmod m$ 最大。注意，$x_i$ **可以为负**，此时 $m\mid (x_i-y_i)$ 且 $0\le y_i<m$。 ## Input 第一行两个正整数 $n,m$。接下来一行 $n$ 个非负整数，代表 $x_i \bmod m$ 的值。 ## Output 第一行一个非负整数 $g$，代表 $\gcd(|x_1|,|x_2|,\cdots,|x_n|)\mod m$ 的可能最大值。接下来一行 $n$ 个整数，代表 $x_i$。 [samples] ## Background 如何输入输出 `__int128`： ```cpp __int128 read() { char c = getchar(); __int128 x = 0; bool f = 0; for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45); for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); if (f) x = -x; return x; } void write(__int128 x, char c = '\0') { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); if (c != '\0') putchar(c); } ``` ## Note **数据范围** **本题采用捆绑测试。** Subtask 1（$30$ pts）：$m$ 是素数。 Subtask 2（$70$ pts）：无特殊限制。对于所有数据，保证 $2\le m \le10^9$，$1\le n\le10^6$。 **关于 Special Judge** 对于每个测试点：如果你输出的格式不正确，你将会获得 $0$ 分。如果你输出的数中有不在 `__int128` 范围的数，可能导致溢出所以你可能无法获得预期的分数。如果你的数列 $x$ 不符合题目给定的 $y$，你将会获得 $0$ 分。如果你的数列 $x$ 不符合你输出的 $g$，你将会获得 $0$ 分。如果你的 $g$ 不为最大，你将会获得 $0$ 分。否则你将获得该测试点的所有分数。

Samples

Input #1

1 10
4

Output #1

6
-6

Input #2

1 10
7

Output #2

7
7

Input #3

2 9
3 3

Output #3

6
12 -6

Input #4

10 7
1 2 3 4 5 6 0 1 2 3

Output #4

6
36 30 24 18 12 6 42 -6 30 24

API Response (JSON)

{
  "problem": {
    "name": "「WHOI-4」ggcd",
    "description": {
      "content": "**本题已新增一组样例，请注意查看。** 小 Y 给了你长度为 $n$ 的数组 $y$ 以及一个正整数 $m$，保证 $0\\le y_i<m$，请你构造一个同样长为 $n$ 的数组 $x$，使得： 1. $x_i$ 在 `__int128` 范围内； 2. $x_i\\bmod m=y_i$； 3. $\\gcd(|x_1|,\\cdots,|x_n|)\\bmod m$ 最大。 注意，$x_i$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8961"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**本题已新增一组样例，请注意查看。**\n\n小 Y 给了你长度为 $n$ 的数组 $y$ 以及一个正整数 $m$，保证 $0\\le y_i<m$，请你构造一个同样长为 $n$ 的数组 $x$，使得：\n\n1. $x_i$ 在 `__int128` 范围内；\n2. $x_i\\bmod m=y_i$；\n3. $\\gcd(|x_1|,\\cdots,|x_n|)\\bmod m$ 最大。\n\n注意，$x_i$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments