洛谷P2714 四元组统计 题解
题目链接：P2714 四元组统计
题意：
有 \(n\) 个正整数 \(a _ i\)，你要统计有多少个四元组满足 \(\gcd(a _ i, a _ j, a _ k, a _ l) = 1\)。
输入格式：
输入包含多组数据。
对于每组数据：第一行一个正整数 \(n\)，接下来一行 \(n\) 个正整数 \(a _ i\)。
输出格式：
若干行，每行对应一个输入数据，表示满足要求的四元组的个数。
数据范围：
\(4 ≤ n ≤ 10000\)，\(1 ≤ a _ i≤ 10000\)，且数据组数不超过 \(100\)。
设 \(f(n)\) 表示 \(n\) 的倍数的出现次数。
初值 \(f(a_i)=k_i\) ，其中 \(k_i\) 表示 \(a_i\) 的出现次数（这里其实是等于 \(n\) 的情况）。
考虑转移，有 \[ f(n) \gets f(n) + \sum_{n \mid d} f(d) \] 这其实是以质因数及其幂次为坐标的 \(\pi(n)\) 维向量上的高维前缀和，参考 Dirichlet 前缀和。
考虑令 \[ f(n) \gets \binom{f(n)}{k} \] 这样 \(f\) 的含义就变成了：满足 \[ \gcd(x_1,x_2,x_3,x_4)\ge n \] 的四元组 \((x_1,x_2,x_3,x_4)\) 的个数，且其中 \(x_1,x_2,x_3,x_4\) 均为 \(n\) 的倍数。
那么我们只需要再做一次高维差分就可以得到答案了，即 \[ f(n) \gets f(n) - \sum_{n \mid d}f(d) \] 可以发现本题还能推广至 \(k\) 元组情况，这个不是本题解要讨论的。
这个高维前缀和/高维差分可以用 Dirichlet 前缀和来做
时间复杂度 \(\mathcal{O}\left(T(n \ln \ln n)\right)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e4 + 15))
char ck[N];
int pcnt, f[N], p[N];
void init(int n = N - 5)
{
rep(i, 2, n)
{
if(!ck[i]) p[++pcnt] = i;
for(int j = 1; j <= pcnt && i * p[j] <= n; j++)
{ ck[i * p[j]] = true; if(i % p[j] == 0) break; }
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int m; init();
while(cin >> m)
{
int x, n = 1;
rep(i, 1, m) { cin >> x; ++f[x]; up(n, x); }
for(int i = 1; i <= pcnt && p[i] <= n; i++)
for(int j = n / p[i]; j > 0; j--) f[j] += f[j * p[i]];
rep(i, 1, n) f[i] = (f[i] - 3) * (f[i] - 2) * (f[i] - 1) * f[i] / 24;
for(int i = 1; i <= pcnt && p[i] <= n; i++)
for(int j = 1; j * p[i] <= n; j++) f[j] -= f[j * p[i]];
cout << f[1] << '\n'; rep(i, 1, n) f[i] = 0;
}
return 0;
}双倍经验：SP4191 MSKYCODE - Sky Code
参考文献：
