【OpenJ_POJ C16D】Extracurricular Sports（构造，找规律）

题目
求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)));

            }

        }

    }

}

巴特西

【OpenJ_POJ C16D】Extracurricular Sports（构造，找规律）

最新文章

热门文章