题解：P10373 [AHOI2024 初中组] 立方根

· · 题解

Luogu - P10373 立方根

楼上大佬都推式子，对于推不出来式子的蒟蒻（我），提供一种找规律的方法。

看到样例提示，开始打表找规律。

找到的规律：

  1. 发现 1 \sim n 立方根向下取整后，是有规律的，会出现固定次数个1，固定次数个2，……，以此类推。

  2. 经过统计，发现立方根每一相邻数字出现的次数的差是一个公差为 6 的等差数列。

开始打表 ing...

int n = 1e3;    
vector <int> v(n + 1);
// 求立方根
for(int i = 1; i <= n; i ++){
    cout << (v[i] = (int)cbrt(1.0*i + 0.5)) << ' ';
}
cout << endl << endl;

// 求连续出现的次数
vector <int> cnt;
int t = 1;
for(int i = 2; i <= n; i ++){
    if(v[i] == v[i - 1]) ++ t;
    else{
        cout << t << endl;
        cnt.push_back(t);
        t = 1;
    }
}
cout << endl << endl;

// 输出连续出现的次数的差值
for(int i = 1; i < cnt.size(); i ++){
    cout << cnt[i] - cnt[i - 1] << endl;
}

得到数据如下：

x \subseteq \{1,1000\},\lfloor \sqrt{x^\frac{1}{3}} \rfloor=\{1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3\cdots\}

其中相同数字连续出现的次数：

$2$ 出现 $19$ 次； $3$ 出现 $37$ 次； $4$ 出现 $61$ 次； $5$ 出现 $91$ 次； $6$ 出现 $127$ 次； $7$ 出现 $169$ 次； $8$ 出现 $217$ 次； $9$ 出现 $271$ 次； $10$ 因为没有完全出现完，不计入统计。 相同数字连续出现的次数相邻项之间的差： $$12,18,24,30,36,42,48,54$$ 可以发现是一个公差为 $6$ 的等差数列。 ------------------ 由此，可以先求出每个数字连续出现的次数。 ```cpp vector <int> u; // u[i]表示第i个数字连续出现的次数 u.push_back(0); // 让下标从1开始 u.push_back(7); for(int i = 2; i <= 10000; i ++){ // x最大1e12，1e12的立方根下取整=10000 u[i] = u[1] + (12 + (12 + (i - 1 - 1) * 6)) * (i - 1) / 2; // 等差数列求和公式：(首项+尾项)*项数/2，尾项(第n项)=首项+(n-1)*公差 } ``` 然后对出现次数求前缀和。 ```cpp vector <ll> sum(u.size()); // u的前缀和 for(int i = 1; i < u.size(); i ++){ sum[i] = sum[i - 1] + u[i]; } ``` 接着，对于每个输入的 $x$ 二分找到第一个大于等于x的前缀和，以确定第x个立方根是几。 ```cpp int l = 1, r = maxn, ans = -1; while(l <= r){ int mid = (l + r) >> 1; if(sum[mid] >= x){ ans = mid; r = mid - 1; // 继续向左找 }else l = mid + 1; } // 循环结束后，ans表示第x个数的立方根是几 ``` 然后分三种情况： 1. 连续立方根中第 $x$ 个数正好是 $1$，直接输出 $1$ 即可。 ```cpp if(ans == 1){ cout << x << '\n'; // x的立方根数字是1时的答案就是1*x } ``` 2. 第 $x$ 个数正好是连续立方根出现的最后一次，此时可以直接计算，答案为 $1 \times u_1 + 2 \times u_2 + \cdots + ans \times u_{ans}$。 ```cpp ll cnt = 0; for(int i = 1; i <= ans; i ++) cnt += i * u[i]; cout << cnt << endl; ``` 3. 第 $x$ 个数是连续立方根中间的数，此时采取分段计算的方法，答案为前面所有连续立方根的和，加上多出来立方根的和，即 $1 \times u_1 + 2 \times u_2 + \cdots + ans \times u_{ans-1} + ans \times (x - sum_{ans-1})$。 ```cpp ll cnt = 0; for(int i = 1; i <= ans - 1; i ++) cnt += i * u[i]; cout << cnt + ans * (x - sum[ans - 1]) << endl; ``` 发现这样每次计算量太大，会超时。 题目中说：**保证给出的 $x_1 \sim x_q$ 单调不降**。所以可以采用一个 $h$ 数组，存储情况 $2$ 中公式的前缀和，即 $h_k=\sum\limits_{i=1}\limits^{k} i \times u_i$，后面接着计算时可以接着前面的，无需重复计算。 ```cpp int k = 1; // 表示h数组该计算哪个位置了 if(ans == 1){ cout << x << '\n'; // x的立方根数字是1时的答案就是1*x }else if(x == sum[ans]){ // 说明x正好是ans出现的最后一次，可以直接计算 // 答案=1*u[1] + 2*u[2] + ... + ans*u[ans]，可以借助前面的h[i]简化计算 for(int i = k; i <= ans; i ++) h[i] = h[i - 1] + i * u[i]; if(k < ans) k = ans; cout << h[ans] << '\n'; }else{ // 先直接计算前面整个的，后面多出来的单独计算 for(int i = k; i <= ans - 1; i ++) h[i] = h[i - 1] + i * u[i]; if(k < ans - 1) k = ans - 1; cout << h[ans - 1] + ans * (x - sum[ans - 1]) << '\n'; // 分段计算 } ``` 由于 $x_{max}=10^{12}$，$\lfloor \sqrt{(10^{12})^\frac{1}{3}} \rfloor=10^4$，所以求 $h$ 数组的循环最多只会执行 $10^4$ 次，显然不会超时。 ------------ 呼~终于做完了，贴个完整代码： ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 10000; void solve() { vector <ll> u; // u[i]表示第i个数字连续出现的次数 u.push_back(0); // 让下标从1开始 u.push_back(7); for(int i = 2; i <= maxn; i ++){ // x最大1e12，1e12的立方根下取整=10000 u.push_back(7 + (12 + (12 + (i - 1 - 1) * 6)) * (i - 1) / 2); // 等差数列求和公式：(首项+尾项)*项数/2，尾项(第n项)=首项+(n-1)*公差 } vector <ll> sum(u.size()); // u的前缀和 for(int i = 1; i < u.size(); i ++){ sum[i] = sum[i - 1] + u[i]; } vector <ll> h(maxn + 1); // h[i]表示当询问的x=i时，输出的答案 int k = 1; // 表示h数组应该记录哪里了 int q; cin >> q; while(q --){ ll x; cin >> x; // 二分找到第一个大于等于x的前缀和，以确定第x个立方根是几 int l = 1, r = maxn, ans = -1; while(l <= r){ int mid = (l + r) >> 1; if(sum[mid] >= x){ ans = mid; r = mid - 1; // 继续向左找 }else l = mid + 1; } // 循环结束后，ans表示第x个数的立方根是几 if(ans == 1){ cout << x << '\n'; // x的立方根数字是1时的答案就是1*x }else if(x == sum[ans]){ // 说明x正好是ans出现的最后一次，可以直接计算 // 答案=1*u[1] + 2*u[2] + ... + ans*u[ans]，可以借助前面的h[i]简化计算 for(int i = k; i <= ans; i ++) h[i] = h[i - 1] + i * u[i]; if(k < ans) k = ans; cout << h[ans] << '\n'; }else{ // 先直接计算前面整个的，后面多出来的单独计算 for(int i = k; i <= ans - 1; i ++) h[i] = h[i - 1] + i * u[i]; if(k < ans - 1) k = ans - 1; cout << h[ans - 1] + ans * (x - sum[ans - 1]) << '\n'; // 分段计算 } } } signed main() { ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0); solve(); return 0; } ``` 管理员大大辛苦啦~ 谢谢大家！