Luogu3708 koishi的数学题

发布于 12 天前  17 次阅读


Link

Sol

乍一看这个题跟[CQOI2007]余数求和那个题挺像。但是实际上数据范围在 10 ^ 6 的级别下整除分块显然不行。

我们还是把它用带余除法的形式重新写一下

f(x) = nx - \sum_{i = 1}^{n} i \times \lfloor \frac{x}{i} \rfloor

唔设g(x)f(x)的差分,那么

g(x) = f(x) - f(x - 1) = n - \sum_{i=1}^{n} i \times (\lfloor \frac{x}{i} \rfloor + \lfloor \frac{x-1}{i} \rfloor)

观察 \lfloor \frac{x}{i} \rfloor\lfloor \frac{x-1}{i} \rfloor 两项

如果 xi 的倍数,那么 \lfloor \frac{x}{i} \rfloor 一定等于 \lfloor \frac{x-1}{i} \rfloor + 1

比如说 i = 3, x = 6,第一项等于 2 ,第二项等于 \lfloor \frac{5}{3} \rfloor + 1 = 2 + 1 = 3

所以括号以内的东西相当于 [i\mid x],就是当且仅当 i 整除 x 的时候你这个式子的值会贡献 1

现在式子就是

g(x) = n - \sigma(x)

所以 f(x) = n \times x - \sum_{i = 1}^{x} \sigma(i)

怎么线性求约数和出个专题讲。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e6 + 5;

int n, tot;
int sig[SIZE], sum[SIZE], prime[SIZE], isPrime[SIZE], low[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void getDiv()
{
    low[1] = isPrime[1] = sum[1] = sig[1] = 1;
    for (int i = 2; i <= n; ++ i) {
        if (!isPrime[i]) {
            sum[i] = sig[i] = i + 1;
            low[i] = prime[++ tot] = i;
        }
        for (int j = 1; j <= tot && i * prime[j] <= n; ++ j) {
            isPrime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                low[i * prime[j]] = low[i] * prime[j];
                sum[i * prime[j]] = sum[i] + low[i * prime[j]];
                sig[i * prime[j]] = sig[i] / sum[i] * sum[i * prime[j]];
                break;
            }
            low[i * prime[j]] = prime[j], sum[i * prime[j]] = prime[j] + 1;
            sig[i * prime[j]] = sig[i] * sig[prime[j]];
        }
    }
}

signed main()
{
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read();
    getDiv();
    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        ans += sig[i];
        printf("%lld ", i * n - ans);
    }
    return 0;
}

朴实沉毅