题目描述

难度分:$2032$

输入$T(\leq 20)$表示$T$组数据。

每组数据输入$X(1 \leq X \leq 9 \times 10^{18})$。

请构造一个长为$10^{100}$的数组$A$，满足：

1. $A[i]$均为正整数。
2. $A[1] = X$。
3. $A[i] \times A[i] \leq A[i-1]$。

输出你可以构造出多少个不同的数组。

输入样例

4
16
1
123456789012
1000000000000000000

输出样例

5
1
4555793983
23561347048791096

算法

动态规划

很容易发现，当数组的某个元素$A[i]$变到$1$的时候，尽管数组的长度达到$10^{100}$，但是后面全都只能是$1$，所以方案已经确定了。所以本质上这道题就是在问：从$X$开始，在题目的限制下有多少种方案可以下降到$1$？

状态定义

$dp[x]$表示以$x$开头的数组有多少种构造方案。

状态转移

第$1$个数是$X$，那么第$2$个数就可以是$[1,[\sqrt{X}]]$（其中$[.]$表示对$.$向下取整，后续省略这个符号），因此状态转移方程为

$dp[X]=\Sigma_{i=1}^{[\sqrt{X}]}dp[i]$

状态转移的时间复杂度是$O(\sqrt{X})$，而需要遍历状态$X$个，算法的整体时间复杂度为$O(X^{1.5})$，对于$X \leq 9 \times 10^{18}$的数据规模而言完全不能接受。此时发现可以利用前缀和进行优化，一边遍历一遍维护$dp$的前缀和数组$s$，此时状态转移就可以变成$O(1)$的

$dp[X]=s[\sqrt{X}]$

时间复杂度变成$O(\sqrt{X})$，对于$X \leq 9 \times 10^{18}$仍然不可接受，需要继续优化。注意到如果第$1$项为$X$，第$3$项为$i$，则第$2$项就确定是区间$[i^2,\sqrt{X}]$中的任何一个数，一共数字的个数为$\sqrt{X}-i^2+1$，可以直接乘，因此状态转移方程为

$dp[X]=\Sigma_{i=1}^{X^{\frac{1}{4}}}(\sqrt{X}-i^2+1)dp[i]$

时间复杂度变为$O(X^{\frac{1}{4}})$，就可以做了。

复杂度分析

时间复杂度

可以先根据题目的数据范围预处理出$dp$数组，由于所有$case$只预处理一次，所以不计入时间复杂度，最终算法的时间复杂度为$O(TX^{\frac{1}{4}})$。

空间复杂度

仅开辟了一个$dp$数组用于存储状态，只用到了$[1,X^{\frac{1}{4}}]$范围内的状态，因此额外空间复杂度仍然是$O(X^{\frac{1}{4}})$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;
typedef long double LD;

int T;
const int N = 100010;
LL f[N];

int main() {
    scanf("%d", &T);
    f[1] = 1;
    for(int i = 2; i <= N - 10; i++){
        for(int j = 1; j <= (int)sqrt((LD)i); j++) {
            f[i] += f[j];
        }
    }
    while(T--) {
        LL x;
        scanf("%lld", &x);
        LL x2 = (LL)sqrt((LD)x);
        int x4 = (int)sqrt((LD)x2);
        LL res = 0;
        for(int i = 1; i <= x4; i++) {
            res += f[i]*(x2 - (LL)i*i + 1);
        }
        printf("%lld\n", res);
    }
    return 0;
}