构造n个数,使其最小公倍数等于其和(n个数互不相等)

文章目录
  1. 1. 背景
  2. 2. 实现
    1. 2.1. 方法2
    2. 2.2. 方法3
  3. 3. 答案
  4. 4. 结论
  5. 5. 音乐

[原创,转载请附网址:http://dongshuyan.top]

背景

昨天去参加了北大acm校赛,其中有一道题就是构造n个数,使其最小公倍数等于其和。(n个数两两不同)

题目链接:点击进入题目或者点击进入题目

例:
input:
3
output:
1 2 3

实现

我真是想了好久呀,基本上一上午都交给这道题了,简单写点心路历程:
感觉这类题一般只有三种做法:
1.每次都搜索,但是时间效率太低,PASS;
2.直接构造,每组数根据特定算出来,例如每次输出:n^0一直到n^n;
3.类似DP,通过之前的推出后面的;

方法2

我刚开始一直在想方法2,通过枚举n个数最后的和(也就是其最小公倍数),通过质因数分解,求其因数,再来凑他们的和。
一开始的思路慢慢变到将最后的和变为使其变为2进制数,然后每一位提出来就保证了每个数都不一样,但是这样一直有问题,没有构造出来。
问题是:这样无法保证他们的最小公倍数还是那个和。

方法3

于是我把思路变到方法3.各种推,真是推导到头大,终于灵光一现。

重要点:
这点我很早就注意到了。这就是每组解,比如 1 2 3,那么1 2 3与6是等价的也就是一旦某一组数对于题目是成立的,并且这组数中含有6,则何以用1 2 3 来代替6.
举一个栗子:1 2 6 9 当n=4时成立,那么 1 2 (1 2 3)9最小公倍数一定等于他们的和,只不过是出现了重复的数,不符合题意罢了。

答案

于是聪明的我想到了如下构造:
我们知道n=3时,可以是 1 2 3 , 所以n=3时,也可以是 6 12 18

大家看到了吗!!!有6!!!
于是就可以变成 1 2 3 12 18!!!奇迹出现了有木有,n=5成立!
于是我可以再乘以6得到 6 12 18 72 108 然后再换 得 1 2 3 12 18 72 108 ,n=7成立,至此奇数项构造成功!

偶数项其实同理,n=4时,1 2 6 9成立(这是我手算的)
我们都乘以6 得到 6 12 36 54 ,然后替换 得到 :1 2 3 12 36 54 ,n=6成立。

结论


1.我是天才

2.构造题大致思路为以上三种

3.等价关系(1 2 3== 6)是关键

4.答案并不唯一,比如(n=4) 1 4 5 10 我们会发现(1 4 5 10==20)于是我们可以开始乘以20,再替换 1 4 5 10 80 100 200 成立

5.n=2时无解 可以证。简写就是,设两个数是a,b, a b 互质,所以ab=a+b 转化为 (a-1)(b-1)=1,所以a=2,b=2,相等了不互质,不符合条件。

音乐