莫比乌斯，欧拉函数练习集合（完结）

$Start\ time：2020/11/16$

$Last\ update\ time: 2020/11/28$

$AC\ 22 / 22$

解方程

$\sum_{d \mid n} f(d) \sigma_{p}(\frac{n}{d}) = \sigma_{q}(n)\\ f * \sigma_{p} = \sigma_{q}\\ 有\sigma_{k} = \sum_{d \mid n} d ^{k} = id_{k} * I\\ f * id_{p} * I = id_{q} * I\\ \sum_{d \mid n} \mu(d) = \mu * I\\ 对上面式子同时卷上一个\mu\\ f * id_{p} = id_{q}\\ 因为id_{k}是一个完全积性函数，所以id_{p} ^{-1} = \mu \times id_{p}\\ id_{k} * (\mu \times id_{p}) = \sum_{d \mid n} d ^k \times \mu(\frac{n}{d}) \times (\frac{n}{d}) ^k = \sum_{d \mid n} \mu(d) = \epsilon\\ f = id_{q} * (\mu \times id_{p})\\ f(n) = \sum_{d \mid n} \mu(d) \times d ^ p \times (\frac{n}{d}) ^{q}\\ f(1) = 1\\ f(n) = n ^ q - n ^ p(n \in primes)\\ f(ab) = f(a) \times f(b) (gcd(a, b) = 1)\\ f(n ^ x) = n ^ q - n ^ p n ^{(x - 1)q} = n ^ {xq} - n ^{p + (x - 1) q} (n \in primes)\\ 然后就可以线性筛了\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e7 + 10, mod = 998244353;

ll prime[N], minnp[N], f[N], cnt, p, q, n;

bool st[N];

ll quick_pow(ll a, int n) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

void init() {
    f[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            f[i] = (quick_pow(i, q) - quick_pow(i, p) + mod) % mod;
            minnp[i] = 1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                minnp[i * prime[j]] = minnp[i] + 1;
                f[i * prime[j]] = f[i / quick_pow(prime[j], minnp[i])] * (quick_pow(prime[j], q * (minnp[i * prime[j]])) - quick_pow(prime[j], p + minnp[i] * q) + mod) % mod;
                break;
            }
            minnp[i * prime[j]] = 1;
            f[i * prime[j]] = f[i] * f[prime[j]] % mod;
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> p >> q;
    init();
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans ^= f[i];
    }
    cout << ans << "\n";
    return 0;
}

求和

$f(n) = \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} gcd(i, j, n)\\ f(n) = \sum_{d \mid n} d \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{\frac{n}{d}}[gcd(i, j, \frac{n}{d}) = 1]\\ \sum_{d \mid n} d \sum_{k \mid \frac{n}{d}} \mu(k) \frac{n}{kd} \frac{n}{kd}\\ T = kd\\ \sum_{T \mid n} \frac{n}{T} \frac{n}{T} \sum_{d \mid T} d \mu(\frac{T}{d})\\ \sum_{T \mid n} \frac{n}{T} \frac{n}{T} \phi(T)\\ \sum_{i = 1} ^{n} \sum_{d \mid i} \frac{i}{d} \frac{i}{d} \phi(d)\\ \sum_{d = 1} ^{n} \phi(d) \sum_{i = 1} ^{\frac{n}{d}} i ^ 2\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

int prime[N], phi[N], cnt, n, mod, inv6;

bool st[N];

int quick_pow(int a, int n) {
    int ans = 1;
    while(n) {
        if(n & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        n >>= 1;
    }
    return ans;
}

void init() {
    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for(int i = 1; i < N; i++) {
        phi[i] = (phi[i] + phi[i - 1]) % mod;
    }
}

unordered_map<int, int> ans_s;

int Djs_phi(int n) {
    if(n < N) return phi[n];
    if(ans_s.count(n)) return ans_s[n];
    int ans = 1ll * n * (n + 1) / 2 % mod;
    for(int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans = (ans - 1ll * (r - l + 1) * Djs_phi(n / l) % mod + mod) % mod;
    }
    return ans_s[n] = ans;
}

int calc(int n) {
    return 1ll * n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d %d", &n, &mod);
    init();
    inv6 = quick_pow(6, mod - 2);
    int ans = 0;
    for(int l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans = (ans + 1ll * (Djs_phi(r) - Djs_phi(l - 1)) * calc(n / l) % mod + mod) % mod;
    }
    printf("%d\n", ans);
    return 0;
}

算术

$\sum_{i = 1} ^{n} \sum_{j = 1} ^{m} \mu(lcm(i, j))\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{m} \mu(\frac{i}{gcd(i, j)}) \mu(j)\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{m} \mu(i) \mu(j) \mu(gcd(i, j))\\ \sum_{d = 1} ^{n} \mu(d) \sum_{i = 1} ^{\frac{n}{d}} \mu(id) \sum_{j = 1} ^{\frac{m}{d}} \mu(jd)[gcd(i, j) = 1]\\ \sum_{d = 1} ^{n} \mu(d) \sum_{k = 1} ^{\frac{n}{d}} \mu(k) \sum_{i = 1} ^{\frac{n}{kd}} \mu(ikd) \sum_{j = 1} ^{\frac{m}{kd}} \mu(jkd)\\ T = kd\\ \sum_{T = 1} ^{n} \sum_{i = 1} ^{\frac{n}{T}} \mu(iT) \sum_{j = 1} ^{\frac{m}{T}} \mu(jT) \sum_{d \mid T} \mu(d) \times \mu(\frac{T}{d})\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int prime[N], mu[N], g[N], f1[N], f2[N], n, m, cnt;

bool st[N];

void init() {
    mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j < N; j += i) {
            g[j] += mu[i] * mu[j / i];
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++) {
            for(int j = i; j <= n; j += i) {
                f1[i] += mu[j];
            }
        }
        for(int i = 1; i <= m; i++) {
            for(int j = i; j <= m; j += i) {
                f2[i] += mu[j];
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += f1[i] * f2[i] * g[i];
        }
        printf("%d\n", ans);
        for(int i = 1; i <= n; i++) {
            f1[i] = 0;
        }
        for(int i = 1; i <= m; i++) {
            f2[i] = 0;
        }
    }
    return 0;
}

Mophues

$\sum_{i = 1} ^{n} \sum_{j = 1} ^{m} f(gcd(i, j))\\ \sum_{d = 1} ^{n} f(d) \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{\frac{m}{d}}[gcd(i, j) = 1]\\ \sum_{d = 1} ^{n} f(d) \sum_{k = 1} ^{\frac{n}{d}} \mu(k) \frac{n}{kd} \frac{m}{kd}\\ \sum_{T = 1} ^{n} \frac{n}{T} \frac{m}{T} \sum_{d \mid T} [f(d) <= p] \mu(\frac{T}{d})\\ 对于所有输入的p，我们按照从小到大排序，对所有的f(d)从小到大排序\\ 用一个树状数组来维护\sum_{d \mid T} [f(d) <= p] \mu(\frac{T}{d})\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef long long ll;

const int N = 5e5 + 10;

int prime[N], mu[N], cnt;

bool st[N];

struct F {
    int f, id;
    bool operator < (const F &t) const {
        return f < t.f;
    }
}a[N];

void init() {
    a[1].id = mu[1] = 1, a[1].f = 0;
    for(int i = 2; i < N; i++) {
        a[i].id = i;
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
            a[i].f = 1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            a[i * prime[j]].f = a[i].f + 1;
            if(i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
}

struct Ask {
    int n, m, p, id;
    bool operator < (const Ask &t) const {
        return p < t.p;
    }
}ask[N];

int ans[N], tree[N];

int lowbit(int x) {
    return x & (-x);
}

void update(int x, int value) {
    while(x < N) {
        tree[x] += value;
        x += lowbit(x);
    }
}

int query(int x) {
    int ans = 0;
    while(x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

signed main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int T;
    scanf("%lld", &T);
    for(int i = 1; i <= T; i++) {
        scanf("%lld %lld %lld", &ask[i].n, &ask[i].m, &ask[i].p);
        ask[i].id = i;
        if(ask[i].n > ask[i].m) {
            swap(ask[i].n, ask[i].m);
        }
    }
    sort(a + 1, a + N);
    sort(ask + 1, ask + 1 + T);
    int now = 1;
    for(int i = 1; i <= T; i++) {
        while(now < N && a[now].f <= ask[i].p) {
            for(int d = a[now].id; d < N; d += a[now].id) {
                update(d, mu[d / a[now].id]);
            }
            now++;
        }
        int res = 0;
        for(int l = 1, r; l <= ask[i].n; l = r + 1) {
            r = min(ask[i].n / (ask[i].n / l), ask[i].m / (ask[i].m / l));
            res += (ask[i].n / l) * (ask[i].m / l) * (query(r) - query(l - 1));
        }
        ans[ask[i].id] = res;
    }
    for(int i = 1; i <= T; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

GuGuFishtion(???)

$\sum_{i = 1} ^{n} \sum_{j = 1} ^{m} \frac{\phi(ij)}{\phi(i) \phi(j)}\\ \phi(ij) = \frac{\phi(i) \phi(j)}{\phi(gcd(i, j))} \gcd(i, j)\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{m} \frac{gcd(i, j)}{\phi(gcd(i, j))}\\ \sum_{d = 1} ^{n} \frac{d}{\phi(d)} \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{\frac{m}{d}}[gcd(i, j) = 1]\\ \sum_{d = 1} ^{n} \frac{d}{\phi(d)} \sum_{k = 1} ^{\frac{n}{d}} \mu(k) \frac{n}{kd} \frac{m}{kd}\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e6 + 10;

int prime[N], phi[N], mu[N], inv[N], n, m, mod, cnt;

ll sum[N];

bool st[N];

ll quick_pow(ll a, int n) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

void init() {
    memset(st, 0, sizeof st);
    cnt = 0;
    mu[1] = phi[1] = inv[1] = 1;
    for(int i = 2; i < N; i++) {
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            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];
        }
    }
    for(int i = 1; i < N; i++) {
        mu[i] = (mu[i - 1] + mu[i] + mod) % mod;
        sum[i] = (sum[i - 1] + 1ll * i * inv[phi[i]] % mod) % mod;
    }
}

ll calc(int n, int m) {
    if(n > m) swap(n, m);
    ll ans = 0;
    for(int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans = (ans + 1ll * (mu[r] - mu[l - 1]) * (n / l) % mod * (m / l) % mod + mod) % mod;
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d", &n, &m, &mod);
        init();
        ll ans = 0;
        if(n > m) swap(n, m);
        for(int l = 1, r; l <= n; l = r + 1) {
            r = min(n / (n / l), m / (m / l));
            ans = (ans + 1ll * (sum[r] - sum[l - 1]) * calc(n / l, m / l) % mod + mod) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

The Boss on Mars

$\sum_{i = 1} ^{n} i ^ 4[gcd(i, n) = 1]\\ \sum_{d \mid n} \mu(d) d ^ 4 \sum_{i = 1} ^{\frac{n}{d}}i ^ 4\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 1e9 + 7;

int prime[N], cnt;

bool st[N];

void init() {
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

int mu(int n) {
    int sum = 0;
    for(int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= n; i++) {
        if(n % prime[i] == 0) {
            n /= prime[i];
            sum++;
            if(n % prime[i] == 0) {
                return 0;
            }
        }
    }
    if(n != 1) sum++;
    return sum & 1 ? -1 : 1;
}

ll calc1(ll n) {
    ll ans = ans = (1ll * 6 * n % mod * n % mod * n % mod * n % mod * n % mod + 1ll * 15 * n % mod * n % mod * n % mod * n % mod + 1ll * 10 * n % mod * n % mod * n % mod - n + mod) % mod;
    ans = ans * 233333335 % mod;
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    init();
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        ll ans = 0;
        for(int i = 1; 1ll * i * i <= n; i++) {
            if(n % i == 0) {
                int temp = mu(i);
                if(temp) {
                    ans = (ans + 1ll * temp * i % mod * i % mod * i % mod * i % mod * calc1(n / i) % mod + mod) % mod;
                }
                temp = mu(n / i);
                if(i * i != n && temp) {
                    ans = (ans + 1ll * temp * (n / i) % mod * (n / i) % mod * (n / i) % mod * (n / i) % mod  % mod * calc1(i) % mod + mod) % mod;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Spare Tire

乱搞后得到一个结论 $a_i = i ^ 2 + i$ 。
$ $\sum_{i = 1} ^{n} (i ^ 2 + i)[gcd(i, m) = 1]\\ \sum_{d \mid m} \mu(d) d^2\sum_{i = 1} ^{\frac{n}{d}} i ^ 2 + \sum_{d \mid m} \mu(d)d \sum_{i = 1} ^{\frac{n}{d}}i\\ 接下来分解质因子，然后暴力统计即可，复杂度最多不过O(T \times 1000)\\$ $

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 1e9 + 7, inv6 = (mod + 1) / 6;

int prime[N], fac[N], tot, cnt, n, m;

bool st[N];

void init() {
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

ll ans = 0;

ll calc1(ll n) {
    return n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
}

ll calc2(ll n) {
    return n * (n + 1) / 2 % mod;
}

void dfs(int sum, int num, int pos) {
    if(pos > tot) {
        ll temp = num & 1 ? -1 : 1;
        ans = ans + temp * sum * sum % mod * calc1(n / sum) % mod + temp * sum * calc2(n / sum) % mod;
        ans = (ans % mod + mod) % mod;
        return ;
    }
    dfs(sum, num, pos + 1);
    dfs(sum * fac[pos], num + 1, pos + 1);
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    while(scanf("%d %d", &n, &m) != EOF) {
        tot = 0;
        for(int i = 1; 1ll * prime[i] * prime[i] <= m; i++) {
            if(m % prime[i] == 0) {
                fac[++tot] = prime[i];
                while(m % prime[i] == 0) {
                    m /= prime[i];
                }
            }
        }
        if(m != 1) {
            fac[++tot] = m;
        }
        ans = 0;
        dfs(1, 0, 1);
        printf("%lld\n", ans);
    }
    return 0;
}

整数对

$\sum_{i = 1} ^{n} \sum_{j = 1} ^{m}[p \mid i \times j]\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{m}[p \mid \gcd(i, p) \times \gcd(j, p)]\\ \sum_{d \mid p} \sum_{i = 1} ^{n}[gcd(i, p) = d] \sum_{k \mid p} \sum_{j = 1} ^{m}[gcd(j, p) = k][p \mid k \times d]\\ \sum_{d \mid p}\sum_{i = 1} ^{\frac{n}{d}}[gcd(i, \frac{p}{d}) = 1]\sum_{k \mid p} \sum_{j = 1} ^{\frac{m}{k}}[gcd(j, \frac{p}{k}) = 1][p \mid k \times d]\\ \sum_{d \mid p} \sum_{x \mid \frac{p}{d}} \mu(x) \frac{n}{xd}\sum_{k \mid p} \sum_{y \mid \frac{p}{k}} \mu(y) \frac{m}{yk}[p \mid k \times d]\\ 先预处理出所有的因子来然后就可以暴力统计答案了\\ 复杂度好像是O(T \times 100 \times 100 \times 100)但是跑不满，最多10 ^ 6左右\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int prime[N], mu[N], cnt, n, m, p;

bool st[N];

vector<int> fac[N];

void init() {
    mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j < N; j += i) {
            fac[j].push_back(i);
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d", &n, &m, &p);
        ll ans = 0;
        for(auto d : fac[p]) {
            ll ans1 = 0;
            for(auto x : fac[p / d]) {
                ans1 += mu[x] * (n / x / d);
            }
            for(auto k : fac[p]) {
                ll ans2 = 0;
                if(1ll * k * d % p) continue;
                for(auto y : fac[p / k]) {
                    ans2 += mu[y] * (m / y / k);
                }
                ans += ans1 * ans2;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

gcd

$\sum_{i = 1} ^{n} \sum_{j = 1} ^{n}gcd(x ^ i - 1, x ^ j - 1)\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} x ^{gcd(i, j)} - 1\\ \sum_{d = 1} ^{n} (x ^ d - 1) \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{\frac{n}{d}}[gcd(i, j) = 1]\\ \sum_{d = 1} ^{n} (x ^ d - 1) \left(2\sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{i}[gcd(i, j) = 1] - 1\right)\\ \sum_{d = 1} ^{n} (x ^ d - 1) \left(2\sum_{i = 1} ^{\frac{n}{d}}\phi(i) - 1\right)\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 1e9 + 7;

int prime[N], phi[N], cnt;

ll sum[N];

bool st[N];

void init() {
    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for(int i = 1; i < N; i++) {
        phi[i] = (phi[i - 1] + phi[i]) % mod;
    }
}

ll quick_pow(ll a, int n) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

ll inv(ll x) {
    return quick_pow(x, mod - 2);
}

ll calc(ll x, int l, int r) {
    if(x == 1) return 0;
    return (quick_pow(x, l) * inv(x - 1) % mod * (quick_pow(x, r - l + 1) - 1) % mod - (r - l + 1) + mod) % mod;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    init();
    scanf("%d", &T);
    while(T--) {
        ll x, n, ans = 0;
        scanf("%lld %lld", &x, &n);
        for(ll l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            ans = (ans + calc(x, l, r) * (2ll * phi[n / l] - 1) % mod) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Clarke and math

$g(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_2} \sum_{i_3 \mid i_2} \dots\sum_{i_k \mid i_{k - 1}}f(i_k)\\ 迪利克%E***7卷积的定义有f * g(n) = \sum_{d \mid n} f(d) f(\frac{n}{d})\\ I * f = \sum_{d \mid n} f(d)\\ 所以g(i) = (I_1 * I_2 * I_3 \dots I_{k - 1} * I_{k}) * f\\ 所以只要做一下迪利克%E***7卷积的快速幂就好了\\ 整体复杂度n \log n \log k\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, k;

struct matrix {
    ll a[N];

    void init() {
        for(int i = 1; i <= n; i++) {
            a[i] = 0;
        }
    }

    void print() {
        for(int i = 1; i <= n; i++) {
            printf("%d%c", a[i], i == n ? '\n' : ' ');
        }
    }
}a, ans, I;

matrix operator * (const matrix & a, const matrix & b) {
    matrix ans;
    ans.init();
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j += i) {
            ans.a[j] = (ans.a[j] + a.a[i] * b.a[j / i] % mod) % mod;
        }
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &k);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a.a[i]);
            I.a[i] = 1;
        }
        ans.init();
        ans.a[1] = 1;
        while(k) {
            if(k & 1) ans = ans * I;
            I = I * I;
            k >>= 1;
        }
        ans = ans * a;
        ans.print();
    }
    return 0;
}

Code

$n = 10000\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n}gcd(i, j) \times(gcd(i, j) - 1) \times cnt_i \times cnt_j\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} gcd(i, j) ^ 2 \times cnt_i \times cnt_j\\ \sum_{d = 1} ^{n} d ^ 2 \sum_{i = 1} ^{\frac{n}{d}} cnt_{id} \sum_{j = 1} ^{\frac{n}{d}} cnt_{jd}[gcd(i, j) = 1]\\ \sum_{d = 1} ^{n} d ^ 2 \sum_{k = 1} ^{\frac{n}{d}} \mu(k) \left(\sum_{i = 1} ^{\frac{n}{kd}}cnt_{ikd} \right) ^ 2\\ T = kd\\ \sum_{T = 1} ^{n} \left(\sum_{i = 1} ^{\frac{n}{T}} cnt_{iT} \right) ^ 2 \sum_{d \mid T} d ^ 2 \mu(\frac{T}{d})\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} gcd(i, j) \times cnt_i \times cnt_j同理可得\\ \sum_{T = 1} ^{n} \left(\sum_{i = 1} ^{\frac{n}{T}} cnt_{iT} \right) ^ 2\sum_{d \mid T} d \mu(\frac{T}{d})\\ \sum_{T = 1} ^{n} \left(\sum_{i = 1} ^{\frac{n}{T}}cnt_{iT} \right) ^ 2 \sum_{d \mid T} (d ^ 2 - d) \mu(\frac{T}{d})\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e4 + 10, mod = 1e4 + 7;

int prime[N], mu[N], num[N], cnt, n;

ll g[N], f[N];

bool st[N];

void init() {
    mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j <= N; j += i) {
            f[j] = (f[j] + (1ll * i * i - i) * mu[j / i] % mod + mod) % mod;
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    while(scanf("%d", &n) != EOF) {
        memset(g, 0, sizeof g);
        memset(num, 0, sizeof num);
        for(int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            num[x]++;
        }
        for(int i = 1; i < N; i++) {
            for(int j = i; j < N; j += i) {
                g[i] = (g[i] + num[j]) % mod;
            }
        }
        ll ans = 0;
        for(int i = 1; i < N; i++) {
            ans =( ans + g[i] * g[i] % mod * f[i]) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

AT5200 [AGC038C] LCMs

$\sum_{i = 0} ^{n - 2} \sum_{j = i + 1} ^{n - 1}lcm(a_i, a_j)\\ 更改下标从1开始\\ \sum_{i = 1} ^{n - 1} \sum_{j = i + 1} ^{n} lcm(a_i, a_j)\\ (\sum_{i = 1} ^{n} \sum_{j = 1} ^{n} lcm(a_i, a_j) - \sum_{i = 1} ^{n} lcm(a_i, a_i)) \times inv2\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} lcm(a_i, a_j) - \sum_{i = 1} ^{n} a_i\\ n = 1e6\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} \frac{i \times j}{gcd(i, j)} \times cnt_i \times cnt_j\\ \sum_{d = 1} ^{n} d \sum_{i = 1} ^{\frac{n}{d}}i \times cnt_{id} \sum_{j = 1} ^{\frac{n}{d}} j\times cnt_{jd}[gcd(i, j) = 1]\\ \sum_{d = 1} ^{n} d \sum_{k = 1} ^{\frac{n}{d}} k ^ 2 \mu(k) \left(\sum_{i = 1} ^{\frac{n}{kd}} i \times cnt_{ikd} \right) ^ 2\\ T = kd\\ \sum_{T = 1} ^{n}T \left(\sum_{i = 1} ^{\frac{n}{T}} i \times cnt_{iT} \right) ^ 2 \sum_{k \mid T} k \mu(k)$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 998244353;

ll sum[N], c[N], n, m, all;

bool st[N];

int prime[N], mu[N], cnt;

ll quick_pow(ll a, ll n, ll mod) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        n >>= 1;
        a = a * a % mod;
    }
    return ans;
}

void init() {
    mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for(int j = 0; j < cnt && i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j < N; j += i) {
            sum[j] = (sum[j] + i * mu[i] % mod + mod) % mod;
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    scanf("%lld", &n), m = 0;
    for(int i = 1; i <= n; i++) {
        ll x;
        scanf("%lld", &x);
        all = (all + x) % mod;
        m = max(x, m);
        c[x]++;
    }
    ll ans = 0;
    for(ll t = 1; t <= m; t++) {
        ll res = 0;
        for(ll i = 1; i <= m / t; i++) {
            res = (res + 1ll * i * c[i * t] % mod) % mod;
        }
        ans = (ans + t * res % mod * res % mod * sum[t] % mod) % mod;
    }
    printf("%lld\n", ((ans - all) * quick_pow(2, mod - 2, mod) % mod + mod) % mod);
    return 0;
}

Dirichlet k -th root

$(f * g)(n) = \sum_{d \mid n}f(d) g(\frac{n}{d})\\ g = f ^ k = f * f * f \dots * f\\ give\ g\ solve\ f\\ f ^ {k ^ {\frac{1}{k}}} = f = g ^{\frac{1}{k}} = g ^{inv(k)}\\ 然后迪利克%E***7卷积快速幂即可\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 998244353;

int n, k;

ll quick_pow(ll a, int n) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

ll inv(int x) {
    return quick_pow(x, mod - 2);
}

struct matrix {
    ll a[N];

    void init() {
        memset(a, 0, sizeof a);
    }

    matrix operator * (const matrix &t) const {
        matrix ans;
        ans.init();
        for(int i = 1; i <= n; i++) {
            for(int j = i; j <= n; j += i) {
                ans.a[j] = (ans.a[j] + a[i] * t.a[j / i] % mod) % mod;
            }
        }
        return ans;
    }
}a, ans;

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d %d", &n, &k);
    k = inv(k);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a.a[i]);
    }
    ans.a[1] = 1;
    while(k) {
        if(k & 1) ans = ans * a;
        a = a * a;
        k >>= 1;
    }
    for(int i = 1; i <= n; i++) {
        printf("%lld%c", ans.a[i], i == n ? '\n' : ' ');
    }
    return 0;
}

GCD of Divisors

$f(n) = \sum_{d \mid n} gcd(d, \frac{n}{d})\\ \sum_{i = 1} ^{n} \sum_{d \mid i} gcd(d, \frac{i}{d})\\ \sum_{d = 1} ^{n} \sum_{d \mid i} gcd(d, \frac{i}{d})\\ \sum_{d = 1} ^{n} \sum_{i = 1} ^{\frac{n}{d}} gcd(d, i)\\ \sum_{d = 1} ^{n} \sum_{i = 1} ^{\frac{n}{d}} \sum_{k \mid gcd(d, i)} \phi(k)\\ \sum_{d = 1} ^{n} \sum_{k \mid d} \phi(k) \frac{n}{kd}\\ \sum_{k = 1} ^{n} \phi(k) \sum_{d = 1} ^{\frac{n}{k}} \frac{n}{k ^ 2 d}\\ 设f(n) = \sum_{i = 1} ^{n} \frac{n}{i}\\ 原式子 = \sum_{k = 1} ^{k \times k <= n} \phi(k) f(\frac{n}{k ^ 2})\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e7 + 10;

ll prime[N], phi[N], cnt;

bool st[N];

void init() {
    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

ll calc(ll n) {
    ll ans = 0;
    for(ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans += (r - l + 1) * (n / l);
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    ll n, ans = 0;
    scanf("%lld", &n);
    for(int i = 1; 1ll * i * i <= n; i++) {
        ans += phi[i] * calc(n / i / i);
    }
    cout << ans << "\n";
    return 0;
}

Absolute Math

$定义c(n) = the\ prime\ n\ have，c(1) = 0, c(2) = 1, c(4) = 1, c(6) = 2 \\ f(n) = \sum_{d \mid n} \mu(d) ^ 2 = 2 ^{c(n)} \\ f(ab) = \frac{f(a) \times f(b)}{f(gcd(a, b))}\\ \sum_{i = 1} ^{m} \frac{f(n) \times f(i)}{f(gcd(n, i))}\\ f(n) \sum_{d \mid n} \frac{1}{f(d)} \sum_{i = 1} ^{\frac{m}{d}} f(id)[gcd(i, \frac{n}{d}) = 1]\\ f(n) \sum_{d \mid n} \frac{1}{f(d)} \sum_{k \mid \frac{n}{d}} \mu(k) \sum_{i = 1} ^{\frac{m}{kd}} f(ikd)\\ T = kd\\ f(n) \sum_{T \mid n} \sum_{i = 1} ^{\frac{m}{T}}f(iT) \sum_{d \mid T} \frac{\mu(\frac{T}{d})}{f(d)}\\ F(m, n) = \sum_{i = 1} ^{m} f(in), g(n) = \sum_{d \mid n} \frac{\mu(\frac{n}{d})}{f(d)}\\ F(m, n) = f(n) \sum_{T \mid n} F(\frac{m}{T}, T) g(T)\\ g = \mu * \frac{1}{f}，是一个积性函数\\ g(1) = 1\\ g(p) = \frac{\mu(p)}{f(1)} + \frac{\mu(1)}{f(p)} = -1 + \frac{1}{2} = -\frac{1}{2}\\ g(p ^ x)[x >= 2] = \frac{\mu(1)}{f(p ^ x)} + \frac{\mu(p)}{f(p ^{x - 1})} = \frac{1}{2} - \frac{1}{2} = 0\\ 然后递归求解，卡卡常\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e7 + 10, mod = 1e9 + 7, inv2 = mod + 1 >> 1;

int prime[N], sum[N], g[N], f[N], cnt;

bool st[N];

void init() {
    f[1] = g[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            f[i] = 2;
            g[i] = mod - inv2;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                f[i * prime[j]] = f[i];
                break;
            }
            f[i * prime[j]] = f[i] * 2;
            g[i * prime[j]] = 1ll * g[i] * g[prime[j]] % mod;
        }
    }
    for(int i = 1; i < N; i++) {
        sum[i] = (f[i] + sum[i - 1]) % mod;
    }
}

ll solve(int m, int n) {
    if(m == 0) return 0;
    if(m == 1) return f[n];
    if(n == 1) return sum[m];
    ll ans = 0;
    //发现m <= 20的时候是较优的……
    if(m <= 20 && 1ll * n * m < N) {
        for(int i=1;i<=m;i++)
            ans = (ans + f[i * n]) % mod;
        return ans;
    }
    for(int i = 1; 1ll * i * i <= n; i++) {
        if(n % i == 0){
            if(g[i]){
                ans = (ans + solve(m / i, i) * g[i] % mod) % mod;
            }
            if(i * i !=n && g[n / i]){
                ans = (ans + solve(m / (n / i), n / i)*g[n / i]) % mod;
            }
        }
    }
    return ans * f[n] % mod;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m;
        scanf("%d %d", &n, &m);
        printf("%lld\n", solve(m, n));
    }
    return 0;
}
/*
    杭电的测评机比自己的老年机跑的还慢……
*/

Counting Divisors

$\sum_{i = 1} ^{n} d(i ^ k)\\ caculte:\sum_{i = l} ^{r} d(i ^ k)\\ d(n)是一个积性函数\\ d(1) = 1\\ d(p) = 2\\ d(p ^ k) = k + 1\\ 然后用区间质数筛就可以得到答案了。$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 998244353;

int prime[N], cnt;

ll a[N], num[N], l, r, k;

bool st[N];

void init() {
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%lld %lld %lld", &l, &r, &k);
        for(int i = 0; i <= r - l; i++) a[i] = l + i, num[i] = 1;
        for(int i = 1; 1ll * prime[i] * prime[i] <= r; i++) {
            ll st = l / prime[i] * prime[i];
            if(st < l) st += prime[i];
            for(ll j = st; j <= r; j += prime[i]) {
                ll res = 0;
                while(a[j - l] % prime[i] == 0) {
                    res++;
                    a[j - l] /= prime[i];
                }
                num[j - l] = num[j - l] * (res * k % mod + 1) % mod;
            }
        }
        for(int i = 0; i <= r - l; i++) {
            if(a[i] != 1) {
                num[i] = num[i] * (k + 1) % mod;
            }
        }
        ll ans = 0;
        for(int i = 0; i <= r - l; i++) {
            ans = (ans + num[i]) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Master of Phi

$f(n) = \sum_{d \mid n} \phi(d) \frac{n}{d}\\ n = \prod_{i = 1} ^{n} p_i ^{a_i}\\ f(n) = (\phi * id)(n)\\ f = \phi * id\\ f * I = \phi * id * I = id * id = id \times \sigma(id)\\ f = (id \times \sigma(id) ) * \mu = \sum_{d \mid n} \mu(d) \times \frac{n}{d} \times \sigma(\frac{n}{d})\\ f(p ^ k) = p ^{k - 1}\times(pk + p - k)\\ 因为f(n)是一个积性函数，所以只要算出每一个质数项然后直接相乘即可\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 998244353;

ll quick_pow(ll a, int n) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T, m;
    scanf("%d", &T);
    while(T--) {
        ll ans = 1, p, k;
        scanf("%d", &m);
        for(int i = 1; i <= m; i++) {
            scanf("%lld %lld", &p, &k);
            ans = (p * k % mod + p - k + mod) % mod * ans % mod * quick_pow(p, k - 1) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Just a Math Problem

$f(k)\ equal\ the\ number\ of\ prime\ factors\ in\ k\\ g(k) = 2 ^{f(k)} = \sum_{d \mid k} \mu(d) ^ 2 \\ \sum_{i = 1} ^{n} g(i)\\ \sum_{i = 1} ^{n} \sum_{d \mid i} \mu(d) ^ 2\\ \mu(d) ^ 2 = \sum_{k ^ 2 \mid d} \mu(k)\\ \sum_{i = 1} ^{n} \sum_{d \mid i} \sum_{k ^ 2 \mid d} \mu(k)\\ \sum_{k = 1} ^{k \times k \leq n} \mu(k) \sum_{k ^ 2 \mid d} \sum_{d \mid i}\\ \sum_{k = 1} ^{k \times k \leq n} \mu(k) \sum_{a = 1} ^{\frac{n}{k ^ 2}} \sum_{b = 1} ^{\frac{n}{a k ^ 2}}\\ \sum_{k = 1} ^{k \times k \leq n} \mu(k) \sum_{i = 1} ^{\frac{n}{k ^ 2}} \frac{n}{i k ^ 2}\\$

#include<cstdio>
typedef long long ll;
const int N=1000010,P=1000000007;
int T,C,tot,p[N/10],i,j,ans,f[N];char mu[N],v[N];ll n;
inline int F(ll n){
  if(n<N)if(f[n])return f[n];
  ll t=0;
  for(ll i=1,j;i<=n;i=j+1)j=n/(n/i),t+=n/i*(j-i+1);
  t%=P;
  if(n<N)f[n]=t;
  return t;
}
int main(){
  for(mu[1]=1,i=2;i<N;i++){
    if(!v[i])mu[i]=-1,p[tot++]=i;
    for(j=0;j<tot&&i*p[j]<N;j++){
      v[i*p[j]]=1;
      if(i%p[j])mu[i*p[j]]=-mu[i];else break;
    }
  }
  for(scanf("%d",&T);T--;printf("Case #%d: %d\n",++C,(ans+P)%P)){
    scanf("%I64d",&n);
    for(ans=0,i=1;i<=n/i;i++)if(mu[i])ans=(ans+F(n/i/i)*mu[i])%P;
  }
  return 0;
}

D. Winter is here

$f(n) = \sum k[gcd(a_{i1}, a_{i2}, a_{i3} \dots a_{i_{k - 1}}, a_{k}) = n]\\ ans = \sum_{i = 2} ^{n} i f(i)\\ F(n) = \sum k[n \mid a_{i1}, n \mid a_{i2}, n \mid _{ai3} \dots n \mid a_{i_{k - 1}}, n \mid a_{i_k}]\\ cnt_n表示是n的倍数的数字的个数\\ = \sum_{i = 1} ^{cnt_n} i C_{cnt_n} ^{i} = cnt_n \times 2 ^{cnt_n - 1}\\ F(d) = \sum_{d \mid n} f(n)\\ f(d) = \sum_{d \mid n} F(n) \mu(\frac{n}{d})\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 1e9 + 7;

int prime[N], mu[N], num[N], f[N], cnt, n;

vector<int> fac[N];

bool st[N];

ll quick_pow(ll a, int n) {
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

void init() {
    mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = 2 * i; j < N; j += i) {
            num[i] += num[j];
        }
        if(num[i]) {
            num[i] = 1ll * num[i] * quick_pow(2, num[i] - 1) % mod;
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j < N; j += i) {
            f[i] = (f[i] + 1ll * num[j] * mu[j / i] % mod + mod) % mod;
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        num[x]++;
    }
    init();
    ll ans = 0;
    for(int i = 2; i < N; i++) {
        ans = (ans + 1ll * i * f[i] % mod) % mod;
    }
    cout << ans << "\n";
    return 0;
}

Battlestation Operational

$\sum_{i = 1} ^{n} \sum_{j = 1} ^{i} \lceil \frac{i}{j} \rceil [gcd(i, j) = 1]\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{i}( \frac{i}{j} + 1)[gcd(i, j) = 1] - \sum_{i = 1} ^{n}\sum_{j = 1} ^{i}[gcd(i, j) = 1, j \mid i]\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{i}(\frac{i}{j} + 1)[gcd(i, j) = 1] - n\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{i} \frac{i}{j}[gcd(i, j) = 1] + \sum_{i = 1} ^{n} \sum_{j = 1} ^{i} [gcd(i, j) = 1] - n\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{i} \frac{i}{j}[gcd(i, j) = 1] + \sum_{i = 1} \phi(i) - n\\ \sum_{i = 1} ^{n} \sum_{j = 1} ^{i} \frac{i}{j}[gcd(i, j)= 1]\\ \sum_{d = 1} ^{n} \mu(d) \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{i} \frac{i}{j}\\ 求解\sum_{i = 1} ^{n} \sum_{j = 1} ^{i} \frac{i}{j} = \sum_{i = 1} ^{n} \sum_{j = i} ^{n} \frac{j}{i}\\ 可以发现这个东西具有区间分块性质\\所以可以利用差分然后求前缀和得到，具体实现看代码\\ 整体复杂度O(n \log n + T \times \sqrt n)\\$

/*
  Author : lifehappy
*/    
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 1e9 + 7;

int prime[N], phi[N], mu[N], f[N], cnt, n;

bool st[N];

void init() {
    mu[1] = phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j < N; j += i) {
            int l = j, r = j + i;
            f[l] = (f[l] + (j / i)) % mod;
            if(r < N) f[r] = (f[r] - (j / i) + mod) % mod;
        }
    }
    for(int i = 1; i < N; i++) {
        phi[i] = (phi[i] + phi[i - 1]) % mod;
        mu[i] = (mu[i] + mu[i - 1] + mod) % mod;
        f[i] = (f[i] + f[i - 1]) % mod;
    }
    for(int i = 1; i < N; i++) {
        f[i] = (f[i] + f[i - 1]) % mod;
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    while(scanf("%d", &n) != EOF) {
        ll ans = 0;
        for(int l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            ans = (ans + 1ll * (mu[r] - mu[l - 1]) * f[n / l] % mod + mod) % mod;
        }
        ans = (ans + phi[n] - n + mod) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}

RXD and math

$\sum_{i = 1} ^{n ^ k} \mu ^ 2(i) \times \sqrt{\frac{n ^ k}{i}}\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int quick_pow(ll a, ll n) {
    a %= mod;
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll n, k, cas = 1;
    while(cin >> n >> k) {
        printf("Case #%d: %d\n", cas++, quick_pow(n, k));
    }
    return 0;
}

GCD?LCM!

$F(n) = \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} [lcm(i, j) + gcd(i, j) \geq n]\\ F(n) = n ^ 2 - \sum_{i = 1} ^{n} \sum_{j = 1} ^{n}[lcm(i, j) + gcd(i, j) < n)]\\ F(n) - F(n - 1) = n ^ 2 - (n - 1) ^ 2 - \sum_{i = 1} ^{n} \sum_{j = 1} ^{n}[lcm(i, j) + gcd(i, j) < n] + \sum_{i = 1} ^{n - 1} \sum_{j = 1} ^{n - 1}[lcm(i, j) + gcd(i, j) < n - 1]\\ F(n) - F(n - 1) = 2 \times n - 1 - \sum_{i = 1} ^{n - 1} \sum_{j = 1} ^{n - 1} [lcm(i, j) + gcd(i, j) = n - 1]\\ g(n) = \sum_{i = 1} ^{n} \sum_{j = 1} ^{n} [lcm(i, j) + gcd(i, j) = n]\\ g(n) = \sum_{d \mid n} \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{\frac{n}{d}}[ijd + d = n ][gcd(i, j) = 1]\\ = \sum_{d \mid n} \sum_{i = 1} ^{\frac{n}{d}} \sum_{j = 1} ^{\frac{n}{d}}[ij = \frac{n}{d} - 1][gcd(i, j = 1)]\\ \sum_{d \mid n} \sum_{i = 1} ^{\frac{n}{d} - 1} \sum_{j = 1} ^{\frac{n}{d} - 1}[ij = \frac{n}{d} - 1][gcd(i, j) = 1]\\ k(n) = \sum_{i = 1} ^{n} \sum_{j = 1} ^{n}[ij = n][gcd(i, j) = 1]\\ k(1) = 1, k(p) = 2,k (p ^ k) = 2，且为积性函数所以可以质数筛得到\\ 然后再通过一次埃筛得到g(n)，即可O(n)得到F(n)\\$

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 258280327;

ll prime[N], k[N], primes[N], g[N], f[N], cnt, n;

bool st[N];

void init() {
    k[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            primes[i] = i;
            prime[++cnt] = i;
            k[i] = 2;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                k[i * prime[j]] = k[i / primes[i]] * 2;
                primes[i * prime[j]] = primes[i] * prime[j];
                break;
            }
            k[i * prime[j]] = k[i] * 2;
            primes[i * prime[j]] = prime[j];
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j < N; j += i) {
            g[j] = (g[j] + k[j / i - 1]) % mod;
        }
    }
    for(int i = 1; i < N; i++) {
        f[i] = (f[i - 1] + 2ll * i - 1 - g[i - 1] + mod) % mod;
    }
    for(int i = 1; i < N; i++) {
        f[i] = (f[i - 1] + f[i]) % mod;
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        printf("%lld\n", f[n]);
    }
    return 0;
}