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

Description

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

Solution

, 考虑朴素做法：筛出 的素数，对于 的每一个数字进行质因数分解 模拟, 预处理长度后拼接上去。我的模拟做法大概是时间复杂度大概是 。
考虑优化：在埃氏筛中，筛法每次遍历素数的所有倍数，显然每次可以 实现上述 的递推。具体做法是，如果对于素数 , 如果，那么显然有 ——相当于在后面先填上 个0，这个过程可以做 次。
举个例子，，那么在埃氏筛的时候，

最后统计答案的时候计算 即可
时间复杂度约为 ——具体我也不知道怎么算

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;
}