前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【OpenJ_POJ C16D】Extracurricular Sports(构造,找规律)

【OpenJ_POJ C16D】Extracurricular Sports(构造,找规律)

作者头像
饶文津
发布2020-05-31 15:47:14
2940
发布2020-05-31 15:47:14
举报
文章被收录于专栏:饶文津的专栏

题目 求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的大整数类写起来比较精简。

代码语言:javascript
复制
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)));
            }
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-07-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档