实力派 题解
hzlqwq
·
·
题解
此题解为官方题解。
前置知识
线性筛质数 / 欧拉函数 / 莫比乌斯函数，欧拉反演，莫比乌斯反演，预处理组合数。
subtask 0
枚举所有选人的方案，暴力计算答案，累积到对应的 k_i 上，预处理好后 O(1) 查询，时间复杂度 O(2^nn\log a_i+q)；实际上跑的飞快。
subtask 1
考虑 dp，令 f_{i,j,k} 表示在前 i 个数中选 j 个数，\gcd 为 k 的方案数，从前向后转移即可，借此预处理答案后 O(1) 查询，时间复杂度 O(n^2a_i+q)。
subtask 2
正解弱化版，可能好想一些吧。
subtask 3
由于值域很小，考虑枚举选了哪几种数：若只选了 2，则 \gcd 为 2；若只选了 3，则 \gcd 为 3；否则 \gcd 为 1。预处理组合数后，对于每种情况分别计算答案，O(1) 查询即可，时间复杂度 O(n+q)。
同时，前三个子任务可以被每次单独回答询问、没有预处理的反演做法通过，而后两个子任务则需要复杂度正确的答案预处理。
subtask 4
留给代码常数过大 / 暴力筛欧拉函数和莫比乌斯函数 / 暴力求因数的部分分。
subtask 5
首先注意到本质不同询问只有 n 个，我们考虑预处理好每个答案后 O(1) 查询；最低实力和最高实力是两个独立的东西，我们分别化简式子，考虑做法：
$$
\sum_{i_1} \sum_{i_2>i_1} \sum_{i_3>i_2} \cdots \sum_{i_x>i_{x-1}} [\gcd(a_{i_1},a_{i_2},a_{i_3},\cdots,a_{i_x})=1]
$$
根据 $[n=1]=\sum_{d\mid n} \mu(d)$，上式可化为：
$$
\sum_{i_1} \sum_{i_2>i_1} \sum_{i_3>i_2} \cdots \sum_{i_x>i_{x-1}} \sum_{d\mid \gcd(a_{i_1},a_{i_2},a_{i_3},\cdots,a_{i_x})} \mu(d)
$$
即：
$$
\sum_{i_1} \sum_{i_2>i_1} \sum_{i_3>i_2} \cdots \sum_{i_x>i_{x-1}} \sum_{d\mid a_{i_1},d\mid a_{i_2},d\mid a_{i_3},\cdots,d\mid a_{i_x}} \mu(d)
$$
将 $d$ 提到前面去：
$$
\sum_{d} \mu(d) \sum_{i_1} \sum_{i_2>i_1} \sum_{i_3>i_2} \cdots \sum_{i_x>i_{x-1}} [d\mid a_{i_1}][d\mid a_{i_2}][d\mid a_{i_3}]\cdots[d\mid a_{i_x}]
$$
可以发现，后面那一串的和式的实际含义是，在 $n$ 个数中选出 $x$ 个数，有多少种方案使它们都是 $d$ 的倍数；那么我们可以先对每个 $d$，预处理出 $d$ 的倍数的个数 $cnt_d$，那么对于每个 $x$，$d$ 的贡献就是 $\begin{pmatrix}cnt_d\\x\end{pmatrix}$；
而因为当 $x>cnt_d$ 时，$\begin{pmatrix}cnt_d\\x\end{pmatrix}=0$，因此对于每个 $d$ 我们只要枚举 $x=1\sim cnt_d$ 进行答案的累加即可，总时间复杂度为 $O(n\log a_i+nd(a_i))$。
$x$ **阶最高实力：**
$$
\sum_{i_1} \sum_{i_2>i_1} \sum_{i_3>i_2} \cdots \sum_{i_x>i_{x-1}} \gcd(a_{i_1},a_{i_2},a_{i_3},\cdots,a_{i_x})
$$
根据 $n=\sum_{d\mid n} \varphi(d)$，上式可化为：
$$
\sum_{i_1} \sum_{i_2>i_1} \sum_{i_3>i_2} \cdots \sum_{i_x>i_{x-1}} \sum_{d\mid \gcd(a_{i_1},a_{i_2},a_{i_3},\cdots,a_{i_x})} \varphi(d)
$$
按相同方式化简可得：
$$
\sum_{d} \varphi(d) \sum_{i_1} \sum_{i_2>i_1} \sum_{i_3>i_2} \cdots \sum_{i_x>i_{x-1}} [d\mid a_{i_1}][d\mid a_{i_2}][d\mid a_{i_3}]\cdots[d\mid a_{i_x}]
$$
注意到上式与 $x$ 阶最低实力中的最终式子，唯一的区别是 $\mu(d)$ 变成了 $\varphi(d)$，那么只要我们线性筛出欧拉函数，问题也就解决了。
程序需进行的流程有：枚举因数 $O(n\log a_i)$，预处理组合数 $O(n\log n)$（或 $O(n)$），线性筛 $O(a_i)$，预处理答案 $O(nd(a_i))$，回答询问 $O(q)$；总时间复杂度 $O(nd(a_i)+q)$。
参考代码：
```cpp
int n, m, p, k, buc[A], maxa, cnt[A], primes[N], mob[A], phi[A], fac[N], ifac[N], mn[N], mx[N];
bool st[A];
inline int qpow(int x, int k)
{
int res = 1;
while (k)
{
if (k & 1)
res = 1ll * res * x % p;
x = 1ll * x * x % p, k >>= 1;
}
return res;
}
inline int c(int n, int m)
{
return 1ll * fac[n] * ifac[m] % p * ifac[n - m] % p;
}
inline void init()
{
for (int i = 1; i <= maxa; i++)
for (int j = 1; i * j <= maxa; j++)
cnt[i] += buc[i * j];
mob[1] = phi[1] = fac[0] = 1;
for (int i = 2; i <= maxa; i++)
{
if (!st[i])
primes[++primes[0]] = i, mob[i] = -1, phi[i] = i - 1;
for (int j = 1; i * primes[j] <= maxa; j++)
{
st[i * primes[j]] = 1;
if (i % primes[j])
mob[i * primes[j]] = -mob[i], phi[i * primes[j]] = phi[i] * (primes[j] - 1);
else
{
mob[i * primes[j]] = 0, phi[i * primes[j]] = phi[i] * primes[j];
break;
}
}
}
for (int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % p;
ifac[n] = qpow(fac[n], p - 2);
for (int i = n - 1; ~i; i--)
ifac[i] = ifac[i + 1] * (i + 1ll) % p;
for (int i = 1; i <= maxa; i++)
for (int j = 1; j <= cnt[i]; j++)
mn[j] = (mn[j] + mob[i] * c(cnt[i], j)) % p, mx[j] = (mx[j] + 1ll * phi[i] * c(cnt[i], j)) % p;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> p;
for (int i = 1, a; i <= n; i++)
cin >> a, buc[a]++, maxa = max(maxa, a);
init();
while (m--)
cin >> k, cout << (mn[k] + p) % p << " " << mx[k] << "\n";
return 0;
}
```