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 個數字 a1,a2,…,aN，ai 代表第 i 個掛飾上面寫的數字。

  • 1≤N≤2×105
  • 1≤ai≤109

Output Format

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

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

例如在 Sample2 之中，可以使用 4 次操作（9 8 7 3 1→9 9 7 3 1→9 9 6 3 1→9 9 6 3 2→9 9 6 3 3）讓最大公因數變成 3，也可以用 4 次操作（9 8 7 3 1→10 8 7 3 1→10 8 8 3 1→10 8 8 4 1→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

IOICamp 2024 Day4 pC

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~36 1≤ai≤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