#P1264. 塔子月赛1-第三题-2333的小清新数论题
塔子月赛1-第三题-2333的小清新数论题
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
Statistics
Related
In following contests:
2333拿到了一个n-排列,即[1,n] 中每个整数恰好出现一次的序列。他想问问要如何摆放这些排列使得前缀和序列的相邻gcd 之和最大?
这样说或许有些抽象。假设我们有一个排列:
P={p1,p2,p3,...,pn}
那么其前缀和数组为:
$s = \{p_1 , p_1+p_2 , p_1+p_2+p_3 , ... , p_1+p_2+...+p_n\}$
相邻gcd数组为:
$G = \{s_1,gcd(s_1,s_2),gcd(s_2,s_3) , ... , gcd(s_{n-1} , s_{n})\}$
现在我们需要确定p1,p2,...,pn 的值,使得如下式子的结果最大化
i=1∑nGi第一行一个整数n(1≤n≤1e5)
输出一行n个整数,代表你构造的结果
n | 占比 |
---|---|
≤8 | 35% |
≤20 | 75% |
≤1e5 | 100% |
输入
5
输出
5 1 2 4 3
样例说明
若最优解的具体方案不唯一,输出任意一个即可。这里再给出一个可能方案:
P2=[4,2,3,1,5]
In following contests:
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.