#P11770. 檐牙覆雪
檐牙覆雪
题目背景
为避免卡常,本题时限为比赛时的 2 倍。
“雨打在窗沿,下坠,一级一级。”
但这次是雪啦!天依与阿绫靠在窗边,赏着乍到的飞雪。
题目描述
还是熟悉的地方:一共有 级窗沿,从高到低编号,最高层编号为 ,最底层编号为 。天依注意到,每一级窗沿上的积雪都可以看作包含若干雪团的可重集合,一开始,第 级窗沿上有一团体积为 的雪,其他窗沿上没有任何积雪。忽然,一阵夹杂着雪的风刮过,片刻间积雪产生了 次变换——
第 次变换中,第 级窗沿上的每一团雪都会被卷起,由于奇妙的物理原因,所有编号是 的整数倍(不包括 自身)的窗沿都会接收到新的积雪。具体地,设一团被卷起的雪体积为 ,则在上述窗沿中,编号最大者会得到一团体积为 的积雪,次大者会得到一团体积为 的积雪,以此类推。最后,被卷起的雪团神奇地回到第 级窗沿,也就是说本次变换后,第 级窗沿上的积雪没有任何变化。
阿绫知道天依正在好奇: 次变换之后,每级窗沿上体积最大的一团雪的总体积是多少呢?既然她们正静静赏雪,就由你来回答这个问题叭!
输入格式
第一行一个整数 ,表示数据组数。
第 行每行一个整数,分别表示每组数据的 。
输出格式
共 行,分别表示每组数据的答案。
5
1
5
3
114514
2000000
1
18
6
18057023450
5575638612615
提示
样例解释
时的终态如下:
第 级窗沿上有体积为 的雪团;
第 级窗沿上有体积为 的雪团;
第 级窗沿上有体积为 的雪团;
第 级窗沿上有体积为 的雪团;
第 级窗沿上有体积为 的雪团;
体积最大值之和为 。
数据规模与约定
本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。
对于 的数据,,。
对于不同的子任务,作如下约定:
子任务编号 | 子任务分值 | ||
---|---|---|---|