2021牛客寒假算法基础集训营2 I 牛牛的“质因数”(数学)

Description

牛牛定义了一个函数F(x)，它表示将x做质因数分解后得到的数字从小到大升序排列，然后将其“拼接”成一个大整数。
例如1500=22355*5,F(1500)=223555。
牛牛现在想要知道 $\sum_{i=2}^{n}F(i)$ 的值。

Solution

$n \leq 4e6$ , 考虑朴素做法：筛出 $[1, 2e3]$ 的素数，对于 $[1, 4e6]$ 的每一个数字进行质因数分解 $O(n\frac{\sqrt{n}}{log_n})$ 模拟, 预处理长度后 $O(logn)$ 拼接上去。我的模拟做法大概是时间复杂度大概是 $O(n\frac{\sqrt{n}}{logn} \cdot logn)$ 。
考虑优化：在埃氏筛中，筛法每次遍历素数的所有倍数，显然每次可以 $O(1)$ 实现上述 $F(x)$ 的递推。具体做法是，如果对于素数 $i$ , 如果 $j = i^{k}$ ，那么显然有 $dp[j] = dp[j] \cdot 10^{len(i)} + i$ ——相当于在后面先填上 $len(i)$ 个0，这个过程可以做 $k$ 次。
举个例子， $12 = 2 \cdot 2 \cdot 3$ ，那么在埃氏筛的时候，

$dp[12] = dp[12] * 10 + 2, dp[12] = 2$
$dp[12] = dp[12] * 10 + 2, dp[12] = 22$
$dp[12] = dp[12] * 10 + 3, dp[12] = 223$

最后统计答案的时候计算 $\sum_{i = 2}^{n} dp[i]$ 即可
时间复杂度约为 $O(nlogn)$ ——具体我也不知道怎么算

Code

#include <bits/stdc++.h>
#pragma GCC optimize(3)
typedef long long ll;
using namespace std;

const int N = 4e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll dp[N];
bool vis[N];
int prime[N], tot;
void solve() {
  std::function<void(int)> init = [&](int n) -> void {
    for(int i = 2; i <= n; i++) {
      if(!vis[i]) {
        prime[++tot] = i; 
        dp[i] = i; // 素数的贡献为本身
        int pre = i;
        int len = 0, need = 1; // 长度
        while(pre) {
          pre /= 10; len++, need *= 10;
        }
        for(int j = 2 * i; j <= n; j += i) {
          vis[j] = 1;
          int cur = j;
          while(cur % i == 0) {
            cur /= i;
            dp[j] = (dp[j] * need % mod + i) % mod;
          }
        }
      }
    }
  };
  int n; cin >> n;
  init(n);
  ll ans = 0;
  for(int i = 2; i <= n; i++) {
    ans += dp[i];
    ans %= mod;
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T = 1; //cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}