如何構造 n 個數使其最小公倍數（LCM）=其和？（ n 個數互不相等）

01-06

北大校賽，想問下大神們是怎麼做的呢？
構造n個數使其最小公倍數（LCM）=其和（n個數互不相等）
描述
As we all know, to pass PE exams, students need to do extracurricular sports, especially jogging. As the result, the Jogging Association in the university is very popular.
There are N students in the Jogging Association. Some run faster while the others run slower. The time it takes for a student to run exactly one lap is called his/her ""lap time"", which is always a positive integer. The lap times of students are distinct from each other. However, running too slow is not allowed for students of the Jogging Association, so each lap time is at most 100 digits.
One day, they make an appointment to jog together. They begin at the same time as well as the same starting point, jog along the circular runway at their own steady speed round and round, not stop until the first time when all of them meet again at the starting point. When they stop, they accidently find that the time they have spent is precisely equal to the time they need if everyone runs a lap one by one, as a relay race.

Now we are curious about the lap times of all the students. Can you guess out any possible solution?
輸入The first line contains an integer T (1 ≤ T ≤ 30), indicating the number of test cases.
For each test case:
A line contains an integer N (2 ≤ N ≤ 200), indicating the number of students.輸出For each test case:
If the solution does not exist, output -1 on a single line;
Otherwise, output one solution with n different integers t1,t2,...,tn, one per line, where ti (1 ≤ ti &< 10^100) indicates the lap time of the i-th student. If there are several solutions, output any one.樣例輸入
1 3
樣例輸出
10 20 30
提示For the three students in the Sample Output, they will stop at time 60, which is precisely equal to the time they need if they run as a relay race.

題目鏈接：
OpenJudge - D:Extracurricular Sports
或者
OpenJudge - C16D:Extracurricular Sports
這題我當時是想了近4h才想出來，想知道那些秒出的大神怎麼做到的？

注意到

$1/2+1/3+(1/2+1/3)/6+cdots+(1/2+1/3)/6^{k-1}+1/6^k=1$

$1/2+1/3+(1/2+1/3)/6+cdots+(1/2+1/3)/6^{k-1}+2/(3 cdot 6^k)+1/(3 cdot 6^k)=1$

上式兩邊同乘以 $6^k=2^k3^k$

$2^{k-1}3^k+2^k3^{k-1}+2^{k-2}3^{k-1}+2^{k-1}3^{k-2}+cdots+3+2+1=6^k$ （共 $2k+1$ 項）

下式兩邊同乘以 $3 cdot 6^k=2^k3^{k+1}$

$2^{k-1}3^{k+1}+2^k3^k+2^{k-2}3^k+2^{k-1}3^{k-1}+cdots+9+6+2+1=3 cdot 6^k$ （共 $2k+2$ 項）

右邊顯然是左邊的LCM，這個不用證了吧。

說一下我的做法吧：

n=2無解，n=3為1 2 3, n=4為1 2 6 9。

n&>4的話先構出n-1的解，把n-1的解中除了1和2以外所有數都乘2，這樣這些數的lcm都乘2了，但和因為1和2沒有加倍所以還差3，那隻要把3再加進解裡面就行了。

比如n=5解為1 2 12 18 3, lcm = sum = 36

n=6時解為1 2 24 36 6 3, lcm = sum = 72

賽後問了昂神 @趙軒昂的做法，聽起來和我們的做法是一樣的，然而現在發現不一樣……還是說一下我們當時的做法吧。

n=2時無解是顯然的。

n=1時一個可行解為1

n=3時一個可行解為1 2 3

n=4時一個可行解為1 2 6 9

上面的解可以通過手構或暴力跑出來，可以發現一些規律，我們再看一下n=5時的一組解：

n=5時一個可行解為1 2 6 18 27

通過上面的幾個例子可以發現一個明顯的規律，我們們設這個數列的第i項為 $a_i$ ，前i項和為 $sum_i$ ,則數列的第i項為：

$a_i =egin{cases} 1 i = 1 \ 2 imes sum_{i - 1} 2 leq i leq n - 1 \ sum_{i - 1} i = n end{cases}$

這樣就做完了。

這相當於構造了一個這樣的數列,其 $a_2 dots a_{n - 1}$ 的通項公式為 $a_i = 2 imes 3^{i - 2}$ ,最後一項 $a_n = 1 + sumlimits_{i = 2} ^ {n - 1} a_i = 3^{n - 2}$ ，這n項的和為 $sumlimits_{i = 1} ^ {n} a_i = a_n + sumlimits_{j = 1} ^ {n - 1} a_j = 2 imes a_n = 2 imes 3^{n - 2}$

我們可以發現這就是這n個數的 $LCM$ (這n個數都只有2、3兩個質因數，且只含一個2，最多的一項含 $n-2$ 個3

這種做法沒有分奇偶，實現起來個人感覺也比前面的幾種做法要簡單。

可以發現n=2是無解的, 對於n=3可以知道一組解是1,2,3, 進一步發現任何w, 2w, 3w都是滿足條件的. 於是就可以利用這個擴展出n為奇數的解. 具體的就是假設當前用了n個數和為x, 那麼新加兩個2x和3x的數, 得到n+2的解. 對於n為偶數的情況, 可以找到n=4的一組解1,2,6,9, 用上述方法就可以類似的擴展出來.

窩的做法

我的方法：

構造n個數，使其最小公倍數等於其和（n個數互不相等）

題主剛打完pku campus 2016吧

@趙軒昂說的很對，稍顯複雜，我們不妨這麼看

1的時候解是1，lcm為1

2無解

4的解是1 2 6 9，lcm為18

那麼對於n個數有解的時候，我在最後加入兩個數 lcm*2 和 lcm*3，剛好和變成了6倍，lcm也變成6倍，如此構造出n+2的解就可以啦。

分奇偶分別寫個高精度

計劃通！

感謝我可愛的隊友lxy童鞋。

我的思路和眾大神有一些不同，一直在用2的n次方構造。

n=2，顯然無解。

n=3，題目中樣例為1 2 3. //lcm=6

n=4，我構造出的解法是1 4 5 10. //lcm=20 這個是硬湊出來的，所以和大神們「故意」算出的1 2 6 9從思路上就有區別了

至此我發現1+2=3，1+4=5，於是開始研究是否可以利用2的n次方進行構造。

n=5，按照2的n次方構造出了1 2 4 7 14. //lcm=28

n=6，一開始嘗試以1 2 4 8開始構造，但是這應該是n=7的解法，參考n=4時捨棄了2，這一組我決定捨棄4，即1 2 8 11 22 44. //lcm=88

由此可以分出n為奇數和偶數兩種情況：

(1)n為奇數，構造1,2,...,2^((n-1)/2)，接下來求他們的和為2^((n+1)/2)-1，以後各項依次乘2.

(2)n為偶數，構造1,2,...,2^(n/2)，但需要捨棄2^((n/2)-1)，並求出他們的和為2^((n/2)+1)-2^((n/2)-1)-1，以後各項依次乘2.

//個人覺得我這個構造方法有點瞎貓碰死耗子，畢竟n=4是我隨意湊出來的，而不是有意而為算出來的。