洛谷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$ 的情况）。
考虑转移，有
这其实是以质因数及其幂次为坐标的 $\pi(n)$ 维向量上的高维前缀和，参考 Dirichlet 前缀和。
考虑令
这样 $f$ 的含义就变成了：满足
的四元组 $(x_1,x_2,x_3,x_4)$ 的个数，且其中 $x_1,x_2,x_3,x_4$ 均为 $n$ 的倍数。
那么我们只需要再做一次高维差分就可以得到答案了，即
可以发现本题还能推广至 $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
参考文献：
