旺崽的博客

要么天赋异禀，要么天道酬勤

0%

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

发表于 分类于 Valine：

题目链接

题目描述

算数基本定理，又称唯一分解定理，算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。即 $N=p_1^{e_1}\cdot p_2^{e_2}…p_m^{e_m}(p_1 < p_2< … p_m)$ 朴素的质因子分解算法就是利用了算数基本定理，依次枚举 $p$ 判断N是否包含素因子 $p$。

牛牛最近对于质因数分解产生了浓厚的兴趣。

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

由于这个结果非常大，所以你只用告诉牛牛最终答案对 $10^9+7$ 取余数的结果即可。

输入描述:

仅一行一个正整数 $n(2 \leq n \leq 4 \times 10^6)$

输出描述:

仅一行，表示答案对 $10^9+7$ 取余数的结果。

示例1

输入

1
3

输出

1
5

示例2

输入

1
10

输出

1
342

一开始就想着暴力算，素筛+质因子分解，这样写跑 $4e6$ 本地要 $3$ 秒，自闭了一会儿我就去忙别的了，最后一个小时突然觉悟了，为什么不记忆化一下每一次算得的答案呢，比如我们暴力算 $20$ 的时候，要算出它所有的质因子:

1
2 2 5

而记忆化的时候我们只需要算 $2*10^{cnt[ans[10]]}+ans[10]$ 即可，什么意思呢？我们记忆化的时候存两个值，一个是 $ans$ (记录某个数算得的答案)，一个是 $cnt$ (记录某个数答案的位数)，我们只需要遍历一遍 $n$ 直接算出所有答案即可，递推公式如下:

为了方便计算我还是选了素筛，把 $j$ 替换成了素数，这样复杂度就是线性筛+一次遍历，一共 $O(2N)$，上面公式直接算也可以，复杂度稍高，应该是 $O(NlogN)$，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll N = 4e6 + 10;
const ll mod = 1e9 + 7;
ll n, k, sum, prime[N / 10], cnt[N], ans[N], vis, p10[1000];
bool isprime[N];

ll f(ll x) {
    ll num = 0;
    while (x) {
        num++;
        x /= 10;
    }
    return num;
}

void Prime() {
    fill(isprime, isprime + N, 1);
    k = 0;
    for (int i = 2; i <= N; i++) {
        if (isprime[i]) {
            prime[k++] = i;
        }
        for (int j = 0; j < k; j++) {
            if (i * prime[j] > N) break;
            isprime[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

void init() {
    p10[0] = 1;
    for (ll i = 1; i < 1000; i++) p10[i] = 10 * p10[i - 1] % mod;
}

int main() {
    cin >> n;
    init();
    Prime();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            if (i * prime[j] > n) break;
            if (i == 1) {
                ans[prime[j]] = prime[j] % mod;
                cnt[prime[j]] = f(prime[j]);
                continue;
            }
            cnt[i * prime[j]] = cnt[i] + cnt[prime[j]];
            if (i < prime[j]) {
                ans[i * prime[j]] = (ans[i] * p10[cnt[prime[j]]] % mod + ans[prime[j]] % mod) % mod;
            } else ans[i * prime[j]] = (ans[prime[j]] * p10[cnt[i]] % mod + ans[i] % mod) % mod;
        }
    }
    for (int i = 2; i <= n; i++) {
        sum = (sum + ans[i]) % mod;
    }
    cout << sum << endl;
    return 0;
}