标签： 莫比乌斯反演

$$ \sum_{1\le i\le n}{\sum_{d|i}{gcd\left( d,\frac{i}{d} \right)}} \\ =\sum_{1\le x\le n}{x\sum_{1\le i\le n}{\sum_{d|i}{\left[ gcd\left( d,\frac{i}{d} \right) =x \right]}}} \\ =\sum_{1\le x\le n}{x\sum_{1\le i\le \lfloor \frac{n}{x^2} \rfloor}{\sum_{d|i}{\left[ gcd\left( d,\frac{i}{d} \right) =1 \right]}}} \\ =\sum_{1\le x\le n}{x\sum_{1\le i\le \lfloor \frac{n}{x^2} \rfloor}{\sum_{d|i}{\sum_{k|d,k|\frac{i}{d}}{\mu \left( k \right)}}}} \\ =\sum_{1\le x\le n}{x\sum_{1\le k\le \lfloor \frac{n}{x^2} \rfloor}{\mu \left( k \right)}\sum_{1\le i\le \lfloor \frac{n}{k^2x^2} \rfloor}{\sum_{d|i}{1}}} \\ \text{设}f\left( x \right) =\sum_{1\le i\le x}{\sum_{d|i}{1}}=\sum_{1\le i\le x}{\lfloor \frac{x}{i} \rfloor} \\ \text{则有}\sum_{1\le x\le n}{x\sum_{1\le k\le \lfloor \frac{n}{x^2} \rfloor}{\mu \left( k \right) f\left( \lfloor \frac{n}{k^2x^2} \rfloor \right)}} \\ \text{令}T=kx,\text{则有} \\ \sum_{\,\,1\le T\le n}{f\left( \lfloor \frac{n}{T^2} \rfloor \right) \sum_{k|T}{\mu \left( k \right) \frac{T}{k}}}=\sum_{1\le T\le n}{f\left( \lfloor \frac{n}{T^2} \rfloor \right) \varphi \left( T \right)} \\ \text{由于}T^2\le n,\text{故}T\le \sqrt{n} \\ \text{则有}\sum_{1\le T\le \sqrt{n}}{f\left( \lfloor \frac{n}{T^2} \rfloor \right) \varphi \left( T \right)} \\ \text{复杂度}O\left( \sum_{1\le i\le \sqrt{n}}{\sqrt{\frac{n}{i^2}}} \right) =O\left( \sqrt{n}\log n \right) \\ \\ $$

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 5e6;
bool isPrime[LARGE + 1];
std::vector<int_t> primes;
int_t factor[LARGE + 1], phi[LARGE + 1];
int_t f(int_t n) {
    int_t i = 1, result = 0;
    // int_t px = n;
    while (i * i <= n) {
        result += (n / i);
        // px--;
        i++;
    }
    int_t k = n / i;
    while (i <= n) {
        // int_t t
        int_t next = n / k;
        result += k * (next - i + 1);
        i = next + 1;
        k--;
    }
    return result;
}
int main() {
    int_t n;
    cin >> n;
    int_t sqrt = ::sqrt(n) + 1;
    memset(isPrime, 1, sizeof(isPrime));
    phi[1] = 1;
    for (int_t i = 2; i <= sqrt; i++) {
        if (isPrime[i]) {
            factor[i] = i;
            primes.push_back(i);
        }
        for (int_t x : primes) {
            if (i * x > sqrt) break;
            isPrime[i * x] = false;
            factor[i * x] = x;
            // factor[i * x] = x;
            if (i % x == 0) break;
        }
    }
#ifdef DEBUG
    for (int_t x : primes) cout << x << endl;
#endif
    phi[1] = 1;
    for (int_t i = 2; i <= sqrt; i++) {
        int_t p = factor[i];
        if (i / p % p == 0)
            phi[i] = phi[i / p] * p;
        else
            phi[i] = phi[i / p] * (p - 1);
    }
    int_t result = 0;
    for (int_t i = 1; i * i <= n; i++) {
        result += f(n / (i * i)) * phi[i];
#ifdef DEBUG

        cout << "phi " << i << " = " << phi[i] << endl;

#endif
    }
    cout << result << endl;
    return 0;
}

$$ E\left( X \right) ,X\text{长度} \\ E\left( X \right) =\sum_{i\ge 1}{P\left( X\ge i \right)},i\text{是长度} \\ =1+\sum_{i\ge 2}{\frac{m^{i-1}-\sum_{1\le j\le m}{\mu \left( j \right) \lfloor \frac{m}{j} \rfloor ^{i-1}}}{m^{i-1}}}\left( \text{枚举长度}i\text{，钦定长度小于}i\text{的全都不互质} \right) \\ 1+\sum_{i\ge 1}{\frac{m^i-\sum_{1\le j\le m}{\mu \left( j \right) \lfloor \frac{m}{j} \rfloor ^i}}{m^i}} \\ 1+\sum_{i\ge 1}{\frac{m^i-m^i-\sum_{2\le j\le m}{\mu \left( j \right) \lfloor \frac{m}{j} \rfloor ^i}}{m^i}} \\ =1-\sum_{1\ge 1}{\frac{\sum_{2\le j\le m}{\mu \left( j \right) \lfloor \frac{m}{j} \rfloor ^i}}{m^i}} \\ 1-\sum_{2\le j\le m}{\mu \left( j \right) \sum_{1\ge 1}{\left( \frac{\lfloor \frac{m}{j} \rfloor}{m} \right) ^i}} \\ =1-\sum_{2\le j\le m}{\mu \left( j \right)}\frac{\lfloor \frac{m}{j} \rfloor}{m}\underset{n\rightarrow \infty}{\lim}\frac{1-\left( \frac{\lfloor \frac{m}{j} \rfloor}{m} \right) ^n}{1-\frac{\lfloor \frac{m}{j} \rfloor}{m}} \\ =1-\sum_{2\le j\le m}{\mu \left( j \right)}\frac{\lfloor \frac{m}{j} \rfloor}{m}\frac{1}{1-\frac{\lfloor \frac{m}{j} \rfloor}{m}} \\ =1-\sum_{2\le j\le m}{\mu \left( j \right)}\frac{\lfloor \frac{m}{j} \rfloor}{m-\lfloor \frac{m}{j} \rfloor} \\ $$

#include <cstring>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t mod = 1e9 + 7;
const int_t LARGE = 1e5;
int_t inv[LARGE + 1];
int_t m;
int_t mu[LARGE + 1];
int_t factor[LARGE + 1];
bool isPrime[LARGE + 1];

int main() {
    memset(isPrime, 1, sizeof(isPrime));
    cin >> m;
    inv[1] = 1;
    for (int_t i = 2; i <= m; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int_t i = 2; i <= m; i++)
        if (isPrime[i]) {
            for (int_t j = i * i; j <= m; j += i) {
                factor[j] = i;
                isPrime[j] = false;
            }
            factor[i] = i;
        }
    mu[1] = 1;
    for (int_t i = 2; i <= m; i++) {
        int_t p = factor[i];
        if (i / p % p == 0)
            mu[i] = 0;
        else
            mu[i] = mu[i / p] * -1;
    }
    int_t result = 1;
    for (int_t i = 2; i <= m; i++) {
        int_t x = m / i;
        result = (result - mu[i] * x % mod * inv[m - x] % mod + mod) % mod;
    }
    cout << result << endl;
    return 0;
}

$$ \sum_{1\le j\le n}{gcd\left( i,j \right) ^clcm\left( i,j \right) ^d\times x_j=b_i} \\ \sum_{1\le j\le n}{gcd\left( i,j \right) ^{c-d}j^dx_j=\frac{b_i}{i^d}} \\ \text{设}f\left( n \right) =n^{c-d}=\sum_{k|n}{g\left( k \right)},\text{则有}g\left( n \right) =\sum_{k|n}{\mu \left( \frac{n}{k} \right) k^{c-d}} \\ \sum_{1\le j\le n}{\sum_{k|gcd\left( i,j \right)}{g\left( k \right)}j^dx_j=\frac{b_i}{i^d}} \\ \sum_{1\le j\le n}{\begin{array}{c} \sum_{k|i\,\,and\,\,k|j}{g\left( k \right) j^dx_j=\frac{b_i}{i^d}}\\ \end{array}} \\ \sum_{k|i}{g\left( k \right) \sum_{k|j,j\le n}{j^dx_j}}=\frac{b_i}{i^d} \\ \text{令}h\left( k \right) =\sum_{k|j,j\le n}{j^dx_j},\text{同时又}i^dx_i=\sum_{i|k,k\le n}{\mu \left( \frac{k}{i} \right) h\left( k \right)},x_i=\frac{\sum_{i|k,k\le n}{\mu \left( \frac{k}{i} \right) h\left( k \right)}}{i^d} \\ \text{故}\sum_{k|i}{g\left( k \right) h\left( k \right) =\frac{b_i}{i^d}} \\ g\left( i \right) h\left( i \right) =\sum_{k|i}{\mu \left( \frac{i}{k} \right) \frac{b_k}{k^d}=w\left( i \right)},\text{如果存在}g\left( i \right) =\text{0且}w\left( i \right) =\text{0,则}h\left( i \right) \text{可取任意值}. \\ \text{如果}g\left( n \right) \text{为0但是}\sum_{k|i}{\mu \left( \frac{i}{k} \right) \frac{b_k}{k^d}}=\text{0不为0，无解。} \\ \\ h\left( i \right) =\frac{\sum_{k|i}{\mu \left( \frac{i}{k} \right) \frac{b_k}{k^d}}}{\sum_{u|i}{\mu \left( \frac{i}{u} \right) u^{c-d}}} \\ \text{故}x_i=\frac{\sum_{i|k,k\le n}{\mu \left( \frac{k}{i} \right) h\left( k \right)}}{i^d} \\ g\left( n \right) =\sum_{k|n}{\mu \left( \frac{n}{k} \right) k^{c-d}} \\ w\left( n \right) =\sum_{k|n}{\mu \left( \frac{n}{k} \right) \frac{b_k}{k^d}} \\ h\left( n \right) =\frac{w\left( n \right)}{g\left( n \right)} \\ $$

#include <cstring>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using int_t = long long int;

const int_t LARGE = 1e5;
const int_t mod = 998244353;
int_t power(int_t base, int_t index);

int_t mu[LARGE + 1];
bool isPrime[LARGE + 1];
int_t factor[LARGE + 1];
int_t g[LARGE + 1];
int_t w[LARGE + 1];
int_t h[LARGE + 1];
int_t n, c, d, q;
void process() {
    static int_t b[LARGE + 1];
    bool fail = false;
    for (int_t i = 1; i <= n; i++) cin >> b[i];
    std::fill(w + 1, w + 1 + n, 0);
    std::fill(h + 1, h + 1 + n, 0);
    for (int_t i = 1; i <= n; i++) {
        int_t f = b[i] * power(i, -d) % mod;
        for (int_t j = 1; j * i <= n; j++) {
            w[j * i] = (w[j * i] + f * mu[j] + mod) % mod;
        }
    }
    for (int_t i = 1; i <= n; i++) {
        if (g[i] == 0) {
            if (w[i] != 0) {
                fail = true;
                break;
            } else {
                h[i] = 0;
            }
        } else {
            h[i] = w[i] * power(g[i], -1) % mod;
        }
    }
    if (fail) {
        cout << -1 << endl;
        return;
    }
    for (int_t i = 1; i <= n; i++) {
        int_t curr = 0;
        for (int_t j = 1; j * i <= n; j++) {
            curr = (curr + mu[j] * h[j * i] % mod + mod) % mod;
        }
        curr = curr * power(i, -d) % mod;
        cout << curr << " ";
    }
    cout << endl;
}
int main() {
    cin >> n >> c >> d >> q;
    memset(isPrime, 1, sizeof(isPrime));
    for (int_t i = 2; i <= n; i++) {
        if (isPrime[i]) {
            for (int_t j = i * i; j <= n; j += i) {
                isPrime[j] = false;
                factor[j] = i;
            }
            factor[i] = i;
        }
    }
    mu[1] = 1;
    for (int_t i = 2; i <= n; i++) {
        int_t factor = ::factor[i];
        if (i / factor % factor == 0)
            mu[i] = 0;
        else {
            mu[i] = mu[i / factor] * -1;
        }
    }
    for (int_t i = 1; i <= n; i++) {
        int_t f = power(i, c - d);
        for (int_t j = 1; j * i <= n; j++) {
            g[j * i] = (g[j * i] + f * mu[j] + mod) % mod;
        }
    }
    while (q--) {
        process();
    }
    return 0;
}

int_t power(int_t base, int_t index) {
    int_t result = 1;
    const auto phi = mod - 1;
    index = (index % phi + phi) % phi;
    base = (base % mod + mod) % mod;
    while (index) {
        if (index & 1) result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}

zz反演题

#include <algorithm>
#include <cstring>
#include <iostream>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 5e6;
const int_t mod = 1000000007;
int_t f[LARGE + 1];
int_t mu[LARGE + 1];
bool isPrime[LARGE + 1];
int_t factor[LARGE + 1];
int_t k;
int_t power(int_t base, int_t index) {
    int_t result = 1;
    while (index) {
        if (index & 1) result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}
void init() {
    memset(isPrime, 1, sizeof(isPrime));
    for (int_t i = 2; i <= LARGE; i++) {
        if (isPrime[i]) {
            factor[i] = i;
            for (int_t j = i * i; j <= LARGE; j += i) {
                factor[j] = i;
                isPrime[j] = false;
            }
        }
    }
    mu[1] = 1;
    for (int_t i = 2; i <= LARGE; i++) {
        if (isPrime[i])
            mu[i] = -1;
        else {
            int_t fac = factor[i];
            if (i / fac % fac == 0) {
                mu[i] = 0;
            } else {
                mu[i] = -mu[i / fac];
            }
        }
    }
    for (int_t i = 1; i <= LARGE; i++) {
        int_t dk = power(i, k);
        for (int_t j = 1; j * i <= LARGE; j++) {
            f[j * i] = (f[j * i] + dk * mu[j] % mod + mod) % mod;
        }
    }
    for (int_t i = 1; i <= LARGE; i++) {
#ifdef DEBUG
        if (i <= 100) {
            cout << "f " << i << " = " << f[i] << endl;
            // cout << "factor " << i << " = " << factor[i] << endl;
            // cout << "mu " << i << " = " << mu[i] << endl;
            
        }
#endif
        f[i] = (f[i - 1] + f[i]) % mod;
    }
}
int_t process(int_t n, int_t m) {
    int_t i = 1;
    if (n > m) std::swap(n, m);
    int_t result = 0;
    while (i <= n) {
        int_t next = std::min(n / (n / i), m / (m / i));
        result = (result +
                  (n / i) * (m / i) % mod * (f[next] - f[i - 1] + mod) % mod) %
                 mod;
        i = next + 1;
    }
    return result;
}

int main() {
    
    int_t T;
    cin >> T >> k;
    init();
    while (T--) {
        int_t n, m;
        cin >> n >> m;
        cout << process(n, m) << endl;
    }
    return 0;
}

$$ \sum_{1\le i\le A}{\sum_{1\le j\le B}{\sum_{1\le k\le C}{\sum_{x|i}{\sum_{y|j}{\sum_{z|k}{\left[ gcd\left( x,y \right) ==1 \right] \left[ gcd\left( x,z \right) ==1 \right] \left[ gcd\left( y,z \right) ==1 \right]}}}}}} \\ \sum_{1\le i\le A}{\sum_{1\le j\le B}{\sum_{1\le k\le C}{\sum_{x|i}{\sum_{y|j}{\sum_{z|k}{\left[ gcd\left( x,y \right) ==1 \right] \left[ gcd\left( x,z \right) ==1 \right] \left[ gcd\left( y,z \right) ==1 \right]}}}}}} \\ \sum_{1\le x\le A}{\sum_{1\le i\le \lfloor \frac{A}{x} \rfloor}{\sum_{1\le y\le B}{\sum_{1\le j\le \lfloor \frac{B}{y} \rfloor}{\sum_{1\le z\le C}{\sum_{1\le k\le \lfloor \frac{C}{z} \rfloor}{\left[ gcd\left( x,y \right) ==1 \right] \left[ gcd\left( x,z \right) ==1 \right] \left[ gcd\left( y,z \right) ==1 \right]}}}}}} \\ \sum_{1\le x\le A}{\sum_{1\le y\le B}{\sum_{1\le z\le C}{\lfloor \frac{A}{x} \rfloor \lfloor \frac{B}{y} \rfloor \lfloor \frac{C}{z} \rfloor \sum_{u|x\ and\ u|y}{\mu \left( u \right)}\sum_{v|x\ and\ v|z}{\mu \left( v \right)}\sum_{w|y\ and\ w|z}{\mu \left( w \right)}}}} \\ \sum_{1\le u\le \min \left( A,B \right)}{\sum_{1\le v\le \min \left( A,C \right)}{\sum_{1\le w\le \min \left( B,C \right)}{\mu \left( u \right) \mu \left( v \right) \mu \left( w \right)}}}\sum_{u|x\ and\ u|y}{\sum_{v|x\ and\ v|z}{\sum_{w|y\ and\ w|z}{\lfloor \frac{A}{x} \rfloor \lfloor \frac{B}{y} \rfloor \lfloor \frac{C}{z} \rfloor}}} \\ \sum_{1\le u\le \min \left( A,B \right)}{\sum_{1\le v\le \min \left( A,C \right)}{\sum_{1\le w\le \min \left( B,C \right)}{\mu \left( u \right) \mu \left( v \right) \mu \left( w \right)}}}\sum_{lcm\left( u,v \right) |x}{\lfloor \frac{A}{x} \rfloor \sum_{lcm\left( u,w \right) |y}{\lfloor \frac{B}{y} \rfloor \sum_{lcm\left( w,v \right) |z}{\lfloor \frac{C}{z} \rfloor}}} \\ \text{设}f\left( p,A \right) =\sum_{p|x\ and\ x\le A}{\lfloor \frac{A}{x} \rfloor} \\ \sum_{1\le u\le \min \left( A,B \right)}{\sum_{1\le v\le \min \left( A,C \right)}{\sum_{1\le w\le \min \left( B,C \right)}{\mu \left( u \right) \mu \left( v \right) \mu \left( w \right) f\left( lcm\left( u,v \right) ,A \right) f\left( lcm\left( u,w \right) ,B \right) f\left( lcm\left( w,v \right) ,C \right)}}} \\ \text{可以注意到不为0的}\mu \left( x \right) \text{的个数不多。} \\ \text{可以构建一张图，图中的点是满足}\mu \left( x \right) \text{不为0的}x\text{，两个点}u,v\text{之间有边当且仅当}\mu \left( u \right) \ne \text{0且}\mu \left( v \right) \ne \text{0且}lcm\left( u,v \right) <\max \left( A,B,C \right) \\ \text{可以断定满足}lcm\left( u,v \right) <10^5\text{的}u,v\text{并不多}. \\ \text{所以直接枚举}lcm\left( u,v \right) \text{建图。} \\ \text{如果要满足}\mu \left( u \right) \ne \text{0且}\mu \left( v \right) \ne \text{0,那么一定满足}\mu \left( uv \right) \ne 0. \\ \text{所以枚举所有}\mu \left( x \right) \ne \text{0且}x\le \max \left( A,B,C \right) \text{的}x,\text{枚举}x\text{的质因子集合}S\text{的一个子集}u\text{，然后再枚举}u\text{的一个子集}v \\ \text{这样}lcm\left( v\times \frac{x}{u},u \right) =x\text{显然成立}. \\ \text{设}S=2\times 3\times 5\times 7 \\ u=2\times 5 \\ \text{则如果一个}v\text{满足}lcm\left( u,v \right) =S,\text{那么}v\text{中一定包含质因子5,7,同时可以包含}u\text{的任何一个子集。} \\ \text{建图之后，去掉所有重边和自环。} \\ \text{然后考虑如何枚举三元环。} \\ \text{直接暴力枚举显然是有问题的。} \\ \text{首先把所有无向边重定向为有向边，对于边}\left( u,v \right) ,\text{如果}deg\left( u \right) <deg\left( v \right) ,\text{则让}u\text{指向}v,\text{如果}deg\left( u \right) =deg\left( v \right) , \\ \text{则让编号小的指向编号大的} \\ \text{可以证明，这样每个点的出度不会超过}\sqrt{n} \\ \text{然后直接对于每个点}u\text{，暴力枚举两条出边}\left( u,v \right) \ \left( u,w \right) ,\text{然后看是否满足}lcm\left( v,w \right) \le \max\text{,如果满足，则说明存在无序三元环} \\ \left( u,v,w \right) ,\text{统计进答案。} \\ \text{这只考虑了三元环三个数均不相同的情况，除此之外还需要考虑两个数相同和三个数都相同的情况。} \\ \\ \\ \\ \\ \ $$

#pragma GCC optimize("O3")
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <assert.h>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t mod = 1e9 + 7;

const int_t LARGE = 1e5;

char mu[LARGE + 1];
int_t factor[LARGE + 1];
std::vector<int_t> pfactor[LARGE + 1];
int f[4][LARGE + 1];

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}
void calc_f(int_t id, int_t A)
{
    for (int_t i = 1; i <= A; i++)
    {
        for (int_t j = 1; j * i <= A; j++)
        {
            f[id][i] = (f[id][i] + A / (j * i)) % mod;
        }
    }
}
int prod(int set, int n)
{
    int prod = 1;
    for (size_t i = 0; i < pfactor[n].size(); i++)
    {
        if (set & (1 << i))
            prod *= pfactor[n][i];
    }
    return prod;
}
int_t process(int_t A, int_t B, int_t C)
{
    struct Pair
    {
        int v1, v2;
    };
    static std::vector<int> graph[LARGE + 1];
    static int degree[LARGE + 1];
    std::vector<Pair> edges;
    memset(f, 0, sizeof(f));
    calc_f(1, A);
    calc_f(2, B);
    calc_f(3, C);
    int max = std::max({A, B, C});
    for (int i = 1; i <= max; i++)
    {
        graph[i].clear();
        degree[i] = 0;
    }
    for (int i = 1; i <= max; i++)
    {
        for (int j = 0; j < (1 << pfactor[i].size()); j++)
        {
            int set = j;
            int c = ((1 << pfactor[i].size()) - 1) & (~set);
            for (int k = 0; k <= j; k++)
            {
                if ((k & j) == k)
                {
                    int v1 = prod(j, i), v2 = prod(k | c, i);
                    edges.push_back({v1, v2});
                    degree[v1] += 1;
                    degree[v2] += 1;
                }
            }
        }
    }
    for (const auto &edge : edges)
    {
        if (degree[edge.v1] < degree[edge.v2] || (degree[edge.v1] == degree[edge.v2] && edge.v1 < edge.v2))
        {
            graph[edge.v1].push_back(edge.v2);
        }
    }

    int_t result = 0;
    ///三个点互异的三元环
    const auto f1 = [&](int a, int b, int c) -> int_t {
        int_t res = 0;
        int p = mu[a] * mu[b] * mu[c];
        int ab = lcm(a, b);
        int bc = lcm(b, c);
        int ca = lcm(c, a);
        //(ab)(bc)(ca)
        res = (res + 1ll * ::f[1][ab] * ::f[2][bc] * ::f[3][ca]) % mod;
        //(ab)(ca)(bc)
        res = (res + 1ll * ::f[1][ab] * ::f[2][ca] * ::f[3][bc]) % mod;
        //(bc)(ab)(ca)
        res = (res + 1ll * ::f[1][bc] * ::f[2][ab] * ::f[3][ca]) % mod;
        //(bc)(ca)(ab)
        res = (res + 1ll * ::f[1][bc] * ::f[2][ca] * ::f[3][ab]) % mod;
        //(ca)(ab)(bc)
        res = (res + 1ll * ::f[1][ca] * ::f[2][ab] * ::f[3][bc]) % mod;
        //(ca)(bc)(ab)
        res = (res + 1ll * ::f[1][ca] * ::f[2][bc] * ::f[3][ab]) % mod;
        return (res * p % mod + mod) % mod;
    };
    for (int i = 1; i <= max; i++)
    {
        auto &curr = graph[i];
        for (int j = 0; j < curr.size(); j++)
        {
            for (int k = j + 1; k < curr.size(); k++)
            {
                if (lcm(curr[j], curr[k]) <= max)
                    result = (result + f1(i, curr[j], curr[k])) % mod;
            }
        }
    }
    //有两个点相同的三元环
    const auto f2 = [&](int a, int b) -> int_t {
        // return 0;
        int_t res = 0;
        int p1 = mu[a] * mu[a] * mu[b];
        int p2 = mu[a] * mu[b] * mu[b];
        int ab = lcm(a, b);
        //(ba) (aa) (ab)
        res = (res + 1ll * p1 * ::f[1][ab] * ::f[2][a] * ::f[3][ab]) % mod;
        //(ab) (ba) (aa)
        res = (res + 1ll * p1 * ::f[1][ab] * ::f[2][ab] * ::f[3][a]) % mod;
        //(aa) (ab) (ba)
        res = (res + 1ll * p1 * ::f[1][a] * ::f[2][ab] * ::f[3][ab]) % mod;
        //(bb) (ba) (ab)
        res = (res + 1ll * p2 * ::f[1][b] * ::f[2][ab] * ::f[3][ab]) % mod;
        //(ba) (ab) (bb)
        res = (res + 1ll * p2 * ::f[1][ab] * ::f[2][ab] * ::f[3][b]) % mod;
        //(ab) (bb) (ba)
        res = (res + 1ll * p2 * ::f[1][ab] * ::f[2][b] * ::f[3][ab]) % mod;
        return (res % mod + mod) % mod;
    };
    for (int i = 1; i <= max; i++)
    {
        auto &curr = graph[i];
        for (int j = 0; j < curr.size(); j++)
        {
            result = (result + f2(i, curr[j])) % mod;
        }
    }
    //三个点都相同的三元环
    const auto f3 = [&](int x) -> int_t {
        return (1ll * mu[x] * mu[x] * mu[x] * f[1][x] * f[2][x] % mod * f[3][x] % mod + mod) % mod;
    };
    for (int_t i = 1; i <= max; i++)
    {
        if (mu[i] != 0)
            result = (result + f3(i)) % mod;
    }
    return result;
}
void init()
{

    for (int_t i = 1; i <= LARGE; i++)
    {
        factor[i] = i;
    }
    for (int_t i = 2; i <= LARGE; i++)
    {
        if (factor[i] == i)
        {
            for (int_t j = i * i; j <= LARGE; j += i)
            {
                factor[j] = i;
            }
        }
    }
    mu[1] = 1;
    for (int_t i = 2; i <= LARGE; i++)
    {
        int_t fact = factor[i];
        if (i / fact % fact == 0)
            mu[i] = 0;
        else
            mu[i] = -mu[i / fact];
    }
    for (int_t i = 2; i <= LARGE; i++)
    {
        if (mu[i] == 0)
            continue;
        int_t curr = i;
        while (curr != 1)
        {
            pfactor[i].push_back(factor[curr]);
            curr /= factor[curr];
        }
    }
}
int main()
{
    init();
    int_t T;
    cin >> T;
    for (int_t i = 1; i <= T; i++)
    {
        int_t A, B, C;
        cin >> A >> B >> C;
        cout << process(A, B, C) << endl;
    }
    return 0;
}