seuOJ536 - Permutation with MAX Score

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：Div.2, 2025

题目描述

一个长度为 $n$ 的排列 $p$ 的得分计算方式如下：

• 首先，你先确定一个正整数 $k$
• 然后，对于每一个大于等于 $2$ 的位置 $i$，计算排列 $p$ 中下标从 $1$ 到 $i-1$ 的所有元素的和，计为 $s_i$
• 如果 $p_i=k\times s_i$，那么排列 $p$ 的得分加 $1$。

给定一个整数 $n$，假如你可以任意选择 $k$，请你求出在所有长度为 $n$ 的排列中，得分最大的排列的得分是多少。

一个长度为 $n$ 的排列 $p$ 是指从 $1$ 到 $n$ 的每个整数恰巧在 $p$ 中出现一次，例如 $[3,1,2]$、$[1]$ 都是排列，但是 $[1,1,3]$、$[3,2,4]$ 都不是排列。

输入格式

第一行，一个整数 $t(1\le t\le 10^5)$，代表数据组数。

对于每组数据，仅输入一个正整数 $n(2\le n\le 10^{18})$，代表排列的长度。

由于这题输入数据的值比较大，所以你可能需要使用能够表示更大数据的数据类型，例如 $\texttt{C++}$ 中的 $\texttt{long long}$。

输出格式

对于每组数据，输出一个整数，代表在确定 $k$ 的情况下，长度为 $n$ 的排列的得分最多是多少。

样例

输入样例

6
2
3
7
916
5201314114514
1000000000000000000

输出样例

1
1
2
9
41
59

样例解释
对于样例第一组数据，选择 $k=2$，此时得分最高的排列为 $[1,{\color{red}2}]$，这个排列的得分为 $1$。

对于样例第三组数据，选择 $k=1$，此时得分最高的排列为 $[2,1,{\color{red}3},{\color{red}6},7,4,5]$。

对于 $i=2$，$1\neq 1\times 2$，所以这个位置不得分。

对于 $i=3$，$3 = 1\times (2+1)$，所以这个位置得分。

对于 $i=4$，$6 = 1\times (2+1+3)$，所以这个位置得分。

对于 $i=5$，$7\neq 1\times (2+1+3+6)$，所以这个位置不得分。

对于 $i=6$，$4\neq 1\times (2+1+3+6+7)$，所以这个位置不得分。

对于 $i=7$，$5\neq 1\times (2+1+3+6+7+4)$，所以这个位置不得分。

最终，这个排列的得分为 $0+1+1+0+0+0=2$。