提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

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

poj 构造 规律
2023-09-11 14:19:25 时间

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

 

　　

相关文章