36 . 侯女神與最大公因數

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

81.5% (22/27)

Submission's AC Ratio

25.8% (84/326)

Tags

ioicamp ioicamp-2024

Description

在一個寧靜的村莊中，住著一位被稱為侯女神的年輕女子，她的愛好讓村人感到十分好奇。不同於一般人的嗜好，侯女神的心靈寄託在數字的神秘之處，她熱愛研究和追求最大公因數的奇妙之處。

村莊裡的人們對侯女神的喜好感到困惑，但也感受到她對數學的熱愛。侯女神的房間裡擺滿了各種數學書籍和數學模型，每當她沉浸在計算和推理的世界時，仿佛整個房間都充滿了數學的氛圍。

有一天，村莊裡舉辦了一場盛大的慶典，慶祝村莊的豐收。侯女神當然也被邀請參加，而這次的慶典上有許多數學元素，讓她感到興奮不已。

在慶典的過程中，侯女神參與了一場有趣的數學比賽，考驗參與者們對最大公因數的理解和應用。她一一解答問題，用簡潔而精確的方式表現出她對最大公因數的深厚知識。村莊裡的人們對她的數學才華讚不絕口。

在慶典的尾聲，村莊的村長感激地送上一份特製的禮物給侯女神。當她打開禮盒時，發現裡面是一串美麗的掛飾，每個掛飾都寫了一個正整數。但是由於工匠的製作疏失，這些數字的最大公因數竟然是 $1$。

最大公因數是 $1$ 對侯女神來說實在是太無聊了，因此工匠需要盡快修改上面的數字來讓最大公因數變成不是 $1$。把一個掛飾上的數字增加 $1$ 或減少 $1$ 都需要 $1$ 單位的時間（但是改完之後數字依然要是正整數），現在 8e7 想知道在花最少時間修改禮物的前提下，這個禮物上的數字序列有可能變成多少？

Input Format

輸入的第一行只有一個數字 $N$，代表禮盒裡面的掛飾數量。

第二行有 $N$ 個數字 $a_1,a_2,\ldots, a_N$，$a_i$ 代表第 $i$ 個掛飾上面寫的數字。

  • $1 \le N \le 2 \times 10^ 5$
  • $1 \le a_i \le 10^ 9$

Output Format

輸出一行，包含 $N$ 個以空白隔開的正整數 $b_1, b_2, \ldots b_N$，表示在最小化修改時間的情況下，可以把掛飾上的數字序列從 $a$ 改成 $b$，並且 $b$ 裡面所有數字的最大公因數不是 $1$。

如果在最小化時間的前提下，有不只一種可能的結果，隨便輸出一個即可。

例如在 Sample2 之中，可以使用 $4$ 次操作（$9\ 8\ 7\ 3\ 1 \to 9\ 9\ 7\ 3\ 1 \to 9\ 9\ 6\ 3\ 1 \to 9\ 9\ 6\ 3\ 2 \to 9\ 9\ 6\ 3\ 3$）讓最大公因數變成 $3$，也可以用 $4$ 次操作（$9\ 8\ 7\ 3\ 1 \to 10\ 8\ 7\ 3\ 1 \to 10\ 8\ 8\ 3\ 1 \to 10\ 8\ 8\ 4\ 1 \to 10\ 8\ 8\ 4\ 2$）讓最大公因數變成 $2$ 因此輸出 9 9 6 3 3 或 10 8 8 4 2 都能獲得 Accepted。

Sample Input 1

3
6 2 4

Sample Output 1

6 2 4

Sample Input 2

5
9 8 7 3 1

Sample Output 2

8 8 6 2 2

Sample Input 3

1
1

Sample Output 3

2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資。 0
2 0~36 $1 \le a_i \le 100$ 22
3 0~74 無特別限制。 78

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2 3
1 1000 262144 65536 1 2 3
2 1000 262144 65536 1 2 3
3 1000 262144 65536 2 3
4 1000 262144 65536 2 3
5 1000 262144 65536 2 3
6 1000 262144 65536 2 3
7 1000 262144 65536 2 3
8 1000 262144 65536 2 3
9 1000 262144 65536 2 3
10 1000 262144 65536 2 3
11 1000 262144 65536 2 3
12 1000 262144 65536 2 3
13 1000 262144 65536 2 3
14 1000 262144 65536 2 3
15 1000 262144 65536 2 3
16 1000 262144 65536 2 3
17 1000 262144 65536 2 3
18 1000 262144 65536 2 3
19 1000 262144 65536 2 3
20 1000 262144 65536 2 3
21 1000 262144 65536 2 3
22 1000 262144 65536 2 3
23 1000 262144 65536 2 3
24 1000 262144 65536 2 3
25 1000 262144 65536 2 3
26 1000 262144 65536 2 3
27 1000 262144 65536 2 3
28 1000 262144 65536 2 3
29 1000 262144 65536 2 3
30 1000 262144 65536 2 3
31 1000 262144 65536 2 3
32 1000 262144 65536 2 3
33 1000 262144 65536 2 3
34 1000 262144 65536 2 3
35 1000 262144 65536 2 3
36 1000 262144 65536 2 3
37 1000 262144 65536 3
38 1000 262144 65536 3
39 1000 262144 65536 3
40 1000 262144 65536 3
41 1000 262144 65536 3
42 1000 262144 65536 3
43 1000 262144 65536 3
44 1000 262144 65536 3
45 1000 262144 65536 3
46 1000 262144 65536 3
47 1000 262144 65536 3
48 1000 262144 65536 3
49 1000 262144 65536 3
50 1000 262144 65536 3
51 1000 262144 65536 3
52 1000 262144 65536 3
53 1000 262144 65536 3
54 1000 262144 65536 3
55 1000 262144 65536 3
56 1000 262144 65536 3
57 1000 262144 65536 3
58 1000 262144 65536 3
59 1000 262144 65536 3
60 1000 262144 65536 3
61 1000 262144 65536 3
62 1000 262144 65536 3
63 1000 262144 65536 3
64 1000 262144 65536 3
65 1000 262144 65536 3
66 1000 262144 65536 3
67 1000 262144 65536 3
68 1000 262144 65536 3
69 1000 262144 65536 3
70 1000 262144 65536 3
71 1000 262144 65536 3
72 1000 262144 65536 3
73 1000 262144 65536 3
74 1000 262144 65536 3
Submit
Back to Top