$$ \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;
}
发表回复