首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

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

02
领券