CONTENT: 线性筛与积性函数 II
DETAIL: 莫比乌斯反演、狄利克雷卷积、杜教筛



BB

其实这个压了很久了，一直没时间复习（预习 T^T
另外数论的话不会特地写solution的，肯定是丢公式啦 （懒QAQ
困死我了 = =

Introduction


Note






LCM Sum - SPOJ LCMSUM

Description
求sum(lcm(i, n))
Sample Input

3
1
2
5

Sample Output

1
4
55

Solution

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int N = 1000000 + 15;

int prime[N], tot;
bool isNotPrime[N];
int phi[N];
ll g[N], f[N];

inline void init() {
    phi[1] = g[1] = f[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!isNotPrime[i]) {
            prime[tot++] = i;
            phi[i] = i - 1;
            f[i] = i;
            g[i] = (ll)i * (i - 1) + 1;
            for(ll k = (ll)i * i; k < N; k *= i) {
                g[k] = g[k / i] + k * (k - k / i);
            }
        }
        for(int j = 0; i * prime[j] < N; j++) {
            isNotPrime[i * prime[j]] = true;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                f[i * prime[j]] = f[i] * prime[j];
                g[i * prime[j]] = g[f[i * prime[j]]] * g[i * prime[j] / f[i * prime[j]]];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
                f[i * prime[j]] = prime[j];
                g[i * prime[j]] = g[i] * g[prime[j]];
            }
        }
    }
}

int main() {
    init();

    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", (g[n] - 1) * n / 2 + n);
    }
}


Crash的数字表格 - HYSBZ 2154

Description
求sum(lcm(i, j))
Sample Input

4 5

Sample Output

122

Solution

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MOD = 20101009;
const int N = (int)1e7 + 5;

int prime[N / 10], tot;
bool isNotPrime[N];
int mu[N];
int sumAuxG[N];

inline void init(int k) {
    mu[1] = 1;
    sumAuxG[1] = 1;
    for(int i = 2; i <= k + 1; i++) {
        if(!isNotPrime[i]) {
            mu[i] = -1;
            prime[tot++] = i;
        }
        sumAuxG[i] = (sumAuxG[i - 1] + ((ll)i * i % MOD * mu[i] + MOD) % MOD) % MOD;
        for(int j = 0; i * prime[j] < k + 1; j++) {
            isNotPrime[i * prime[j]] = true;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            } else {
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
}

inline int funcH(int n, int m) {
    return (((ll)n * (n + 1) / 2 % MOD) * ((ll)m * (m + 1) / 2 % MOD)) % MOD;
}

inline int funcG(int n, int m) {
    int ret = 0;
    for(int i = 1, last; i <= n; i = last + 1) {
        last = min(n / (n / i), m / (m / i));
        ret = (ret + (ll)(sumAuxG[last] - sumAuxG[i - 1] + MOD) * funcH(n / i, m / i)) % MOD;
    }
    return ret;
}

inline int funcF(int n, int m) {
    int ret = 0;
    for(int i = 1, last; i <= n; i = last + 1) {
        last = min(n / (n / i), m / (m / i));
        ret = (ret + (ll)(i + last) * (last - i + 1) / 2 % MOD * funcG(n / i, m / i)) % MOD;
    }
    return ret;
}

int main() {
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        if(n > m) {
            swap(n, m);
        }
        init(n);
        printf("%d\n", funcF(n, m));
    }
}


【模板】杜教筛（Sum） - luogu P4213

Description
求欧拉函数与莫比乌斯函数前缀和，n <= 2^31 - 1
Sample Input

6
1
2
8
13
30
2333

Sample Output

1 1
2 0
22 -2
58 -3
278 -3
1655470 2

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 3e6 + 5;
const ll inf = 1e18+ 5;

unordered_map<int, ll> mp_mu;
unordered_map<int, ll> mp_phi;

bool isprime[N];
int tot;
int prime[N];
int mu[N], phi[N];
ll arr_sum_mu[N], arr_sum_phi[N];

ll getSumMu(int n) {
    if(n < N)             return arr_sum_mu[n];
    if(mp_mu.count(n))    return mp_mu[n];

    ll sum_con_fg = 1;
    ll sum_mu = sum_con_fg;
    for(int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);

        ll sum_g = r - l + 1;
        sum_mu -= sum_g * getSumMu(n / l);
    }
    return mp_mu[n] = sum_mu;
}

ll getSumPhi(int n) {
    if(n < N)               return arr_sum_phi[n];
    if(mp_phi.count(n))     return mp_phi[n];

    ll sum_con_fg = (ll)n * (n + 1) / 2;
    ll sum_phi = sum_con_fg;
    for(int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);

        ll sum_g = r - l + 1;
        sum_phi -= sum_g * getSumPhi(n / l);
    }
    return mp_phi[n] = sum_phi;
}

inline void init() {
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    mu[1] = 1, phi[1] = 1;
    arr_sum_mu[1] = 1, arr_sum_phi[1] = 1;
    tot = 0;

    for(int i = 2; i < N; i++) {
        if(isprime[i]) {
            prime[tot++] = i;
            phi[i] = i - 1;
            mu[i] = -1;
        }

        for(int j = 0; j < tot && prime[j] * i < N; j++) {
            isprime[i * prime[j]] = false;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                mu[i * prime[j]] = 0;
                break;
            }

            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            mu[i * prime[j]] = -mu[i];
        }

        arr_sum_mu[i] = arr_sum_mu[i - 1] + mu[i];
        arr_sum_phi[i] = arr_sum_phi[i - 1] + phi[i];
    }
}

int main() {
    init();

    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        printf("%lld %lld\n", getSumPhi(n), getSumMu(n));
    }
}