102436: [AtCoder]ABC243 G - Sqrt
Description
Score : $600$ points
Problem Statement
We have a sequence of length $1$: $A=(X)$. Let us perform the following operation on this sequence $10^{100}$ times.
Operation: Let $Y$ be the element at the end of $A$. Choose an integer between $1$ and $\sqrt{Y}$ (inclusive), and append it to the end of $A$.
How many sequences are there that can result from $10^{100}$ operations?
You will be given $T$ test cases to solve.
It can be proved that the answer is less than $2^{63}$ under the Constraints.
Constraints
- $1 \leq T \leq 20$
- $1 \leq X \leq 9\times 10^{18}$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$T$ $\rm case_1$ $\vdots$ $\rm case_T$
Each case is in the following format:
$X$
Output
Print $T$ lines. The $i$-th line should contain the answer for $\rm case_i$.
Sample Input 1
4 16 1 123456789012 1000000000000000000
Sample Output 1
5 1 4555793983 23561347048791096
In the first case, the following five sequences can result from the operations.
- $(16,4,2,1,1,1,\ldots)$
- $(16,4,1,1,1,1,\ldots)$
- $(16,3,1,1,1,1,\ldots)$
- $(16,2,1,1,1,1,\ldots)$
- $(16,1,1,1,1,1,\ldots)$
Input
题意翻译
你现在有一个数 $X$。 每次你可以进行以下操作： - 设末尾的数是 $Y$。在 $1$ 到 $\sqrt{Y}$ 中选取一个数 $Z$。 - 把 $Z$ 加到序列的末尾。 如此进行 $10^{100}$ 次操作，问一共有多少种可能的情况。 可以证明，答案不超过 $2^{63}-1$。 $X \le 9 \times 10^{18}$。多组数据。Output
问题描述
我们有一个长度为$1$的序列$A=(X)$。让我们对这个序列执行$10^{100}$次以下操作。
操作：将$Y$设为$A$的最后一个元素。从$1$到$\sqrt{Y}$（包括）中选择一个整数，并将其添加到$A$的末尾。
可以由$10^{100}$次操作得到的序列有多少个？
你需要解决$T$个测试用例。
在约束条件下，可以证明答案小于$2^{63}$。
约束
- $1 \leq T \leq 20$
- $1 \leq X \leq 9\times 10^{18}$
- 输入中的所有值都是整数。
输入
输入从标准输入中给出，格式如下：
$T$ $\rm case_1$ $\vdots$ $\rm case_T$
每个用例的格式如下：
$X$
输出
打印$T$行。 第$i$行应包含$\rm case_i$的答案。
样例输入1
4 16 1 123456789012 1000000000000000000
样例输出1
5 1 4555793983 23561347048791096
在第一个用例中，可以通过操作得到以下五个序列。
- $(16,4,2,1,1,1,\ldots)$
- $(16,4,1,1,1,1,\ldots)$
- $(16,3,1,1,1,1,\ldots)$
- $(16,2,1,1,1,1,\ldots)$
- $(16,1,1,1,1,1,\ldots)$