埃筛做法

首先什么是埃筛：

#include <stdio.h>
#include <string.h>
const int N = 100 + 8;
int isPrime[N];
void sieve() {
    memset(isPrime, -1, sizeof isPrime);
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i < N; ++i)
        if (isPrime[i])
            for (int j = 2; i * j < N; ++j) isPrime[i * j] = 0;
}
int main() {
    sieve();
    for (int i = 2; i < N; ++i)
        if (isPrime[i]) printf("%d ", i);
    return 0;
}

可以发现，在朴素的埃筛里，对于每一个合数，它会被每个它的质因数筛到。而如果是质数，他的质因数合并就是它本身。

所以只需要实时更新下每个数的质因数合并即可。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 4e6 + 7;
const int mod = 1e9 + 7;
bitset<N> isPrime;
ll ans[N];
int main() {
    ll w[10] = {1};
    rep(i, 1, 9) w[i] = w[i - 1] * 10;
    ll n;
    sc(n);
    isPrime.set();
    rep(i, 2, n) {
        if (isPrime[i]) {
            ans[i] = i;
            int len = log10(i) + 1;
            for (int j = 2; i * j <= n; ++j) {
                int now = i * j;
                isPrime[now] = 0;
                do {
                    ans[i * j] = (ans[i * j] * w[len] % mod + i) % mod;
                    now /= i;
                } while (now % i == 0);
            }
        }
    }
    ll res = 0;
    rep(i, 2, n) res = (res + ans[i]) % mod;
    pr(res);
    return 0;
}

这种做法时间复杂度，本题300ms

欧拉筛 + DFS

欧拉筛是近似线性的筛法，这意味着不能像埃筛一样，对每个数更新答案。

但是可以从另一个角度出发：

  • 对于每个质数，它的质因数合并就是它本身。
  • 对于每个合数，它的质因数合并是它所有质因数的拼接。
  • 反过来说，可以用所有的质因数乘出来所有的数，对于质因数合并，也就是拼接。
  • 所以每个数和它的质因数合并都是一一对应的。

所以，可以直接去尝试拼接就可以了，如果是在所求范围内的，就加上权重即可，这也是唯一分解定理的逆向应用，非常巧妙。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 4e6 + 7;
const int mod = 1e9 + 7;
bitset<N> isPrime;
int prim[N + 10];
int pn = 0;
ll ans, n;
int w[10] = {1};
int pw[N];
void pre(int N) {
    rep(i, 1, 9) w[i] = w[i - 1] * 10;
    isPrime.set();
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) pw[pn] = w[int(log10(i) + 1)], prim[pn++] = i;
        for (int j = 0; j < pn && i * prim[j] <= N; ++j) {
            isPrime[i * prim[j]] = 0;
            if (i % prim[j] == 0) break;
        }
    }
}
void dfs(int pos, ll key, ll val) {
    ans = (ans + val) % mod;
    for (int i = pos; i < pn; ++i) { // merge with bigger prime num
        if (key * prim[i] > n) return;
        dfs(i, key * prim[i], (val * pw[i] % mod + prim[i]) % mod);
    }
}
int main() {
    sc(n);
    pre(n);
    for (int i = 0; i < pn && prim[i] <= n; ++i)
        // start dfs from each prime num
        dfs(i, prim[i], prim[i]);
    pr(ans);
    return 0;
}

这种做法时间复杂度，本题70ms