题目
求n个互不相同的数,满足其和为其lcm。
我们把lcm看成一个线段,分割成长度不同的n份。
当然分法有很多,我们只需要构造一个好想好写的。
先分成两个二分之一,取其中一个二分之一再分成1/3和2/3,接下来每次取1/3的分成1/3和2/3。
1
1/2 1/2
1/2 2/6 1/6
1/2 2/6 2/18 1/18
最短的是1/18的这份,我们让它为1。则可算出其它的长度:9 6 2 1。
所以1,2为最短的两个,接下来每个数就是前面的数的和的两倍,最后一个数是前面所有的数之和。
再长一点:1 2 6 18 54 81
可以发现,前面两个数是1,2,接下来是前面一个数的3倍,最后一个数是3的n-2次方。
令$a[0]=1,a[i]=2*3^{i-1}$,答案就是a[0]到a[n-2],a[n-1]/2。
用java的大整数类写起来比较精简。
import java.io.*;
import java.math.*;
import java.util.*;
public class Main{
//a[i]=1 2 6 18 54 162
static BigInteger a[]=new BigInteger[250];
public static void main(String[] args){
Scanner cin= new Scanner(System.in);
a[0]=BigInteger.valueOf(1);
a[1]=BigInteger.valueOf(2);
for(int i=2;i<=200;i++)
a[i]=a[i-1].multiply(BigInteger.valueOf(3));
int t=cin.nextInt();
for(int i=1;i<=t;i++){
int n=cin.nextInt();
if(n==2)System.out.println(-1);
else{
for(int j=0;j<n-1;j++)
System.out.println(a[j]);
System.out.println(a[n-1].divide(BigInteger.valueOf(2)));
}
}
}
}