CSP40 D题：C形阵

题目化简

根据C形阵的性质推出$B^2=AC,F^2=EG$和$B=F$。
可以将所有6个变量（$F=B$恒成立，不把$F$看作变量）用$B,C,E$表示：

$$\begin{array}{rl}& A=\frac{B^2}{C}\\ & D=\frac{B^3}{CE}\\ & G=\frac{B^2}{E}\end{array}\text{\hspace{1em}(1)}$$

从这个式子中也能发现$C,E$是对称关系，从图中也可以看出。

由于所有变量都是整数，还有三个约束为：$B^2$能被$C$（和$E$）整除，$B^3$能被$CE$整除。
对于op==0的情况，需要枚举每个$B$(从1到n)，找出满足条件的$C,E$，并计算$D=\frac{B^3}{CE}$的累加和即可；对于op==1的情况，要求至少有6个不同的数就是要求除$B,F$外的数都互不相同。
记给定$B$时所有$D$的总和为$f(B)$，这是op==0时的答案；记互不相同时所有$D$的和为$F(B)$，这是op==1时的答案。

完美C形阵的特点

组合问题计数，用容斥原理尝试分析。列出有变量重复的情况，先考虑两两重复（如$B=C）$，再考虑多个变量相等（如$B=C=E$）。
两两相等有$C_6^2=15$种情况。由于变量之间并非独立（有(1)的约束），所以这些情况一定有等价的情形。把这些等价情形都转换为$B,C,E$之间的关系：

化简后$B,C,E$的关系	对应的原始等式（两两相等）
$C=B$	$A=B,B=C,A=C,D=G$
$E=B$	$A=C,B=E,B=G,E=G$
$C=E$	$A=E,C=G,A=G,C=E$
$CE=B^2$	$B=D,C=G$
$C^{2}E=B^3$	$C=E$
$E^{2}C=B^3$	$D=E$

或许根据这个系统的原本的约束数量，就能够计算出这15种情况一定会归为这6种可能（而不需要枚举）。或许需要代数学的知识。另外，约束(1)是齐次的，可能帮助推导。

这样，两个变量相等的所有情况被我们化简为上面的6种，这六种情况分别记作$P_i$，构成集合$P$。设$h_i(P_i;B)$是第$i$种情况下的$D$的和，$h_{i,j}(P_i,P_j;B)$是第$i,j$两种情况同时发生时的$D$的和。
根据容斥原理，

$$\begin{array}{rl}F(B)& =f(B)-\sum _i{h}_i+\sum _{i,j}{h}_{i,j}-\cdots +\sum _{i_1,i_2,\dots ,i_6}{h}_{i_1,i_2,\dots ,i_6}\end{array}\text{\hspace{1em}(2)}$$

下面考虑多个变量（至少3个）都相等的情况。令上面两两相等的6种情况中至少两个等式同时成立，发现：全部都会得到$C=B=E$，即全部变量都由$B$决定（只有一个自由度），此时，$D=B$（价值与大小相等）。
这说明减去上面的六种情况时（对应式2的$-{\sum }_i{h}_i$项），这个唯一解被我们减去了6次，我们应该只减掉它一次，所以需要加回5次这个情况的$h$值（即$B$），共需要加$5B$。

也可以继续用式2的形式化方式计算。但按照容斥原理思想做更简单。

由于$B$和$E$的对称性，$h_1=h_2,h_5=h_6$。式2化简为

$$\begin{array}{rl}F(B)& =f(B)-(h_1+h_2+\cdots +h_6)+5B\\ & =f(B)-2h_1-h_3-h_4-2h_5+5B\end{array}$$

计算优化

积性函数

求解 $f(B)$ 和 $h_i(B)$ 的关键在于分析其函数性质。由于题目的约束条件全部基于整除关系，这天然契合算术基本定理。
设 $B$ 的唯一分解为 $\prod p_i^{k_i}$。
条件 $C\mid B^2$、$E\mid B^2$ 及 $CE\mid B^3$ 等价于对 $C$ 和 $E$ 的质因子分解 $C=\prod p_i^{c_i}$， $E=\prod p_i^{e_i}$ 中每个质因子 $p_i$ 的指数提出独立的不等式约束：

$$\{\begin{array}{l}{c}_i\le 2k_i\\ e_i\le 2k_i\\ c_i+e_i\le 3k_i\end{array}$$

这说明不同质因子之间的约束是完全独立的。同时，对应的贡献 $D=\frac{B^3}{CE}=\prod p_i^{3k_i-(c_i+e_i)}$ 也是按质因子连乘的。
因此，总和 $f(B)$ 满足乘法分配律，即对于任意互质的正整数 $n,m$，有 $f(n\times m)=f(n)\times f(m)$。同理，各部分交集的和 $h_i(B)$ 也是积性函数。

既然是积性函数，我们只需推导 $B=p^k$（即单一质数次幂）时的通项公式即可。
当 $B=p^k$ 时，令 $C=p^c$，$E=p^e$，此时 $D=p^{3k-(c+e)}$。令 $x=c+e$。

对于 $f(p^k)$：
枚举 $x$ 的值，统计有多少对 $(c,e)$ 满足约束。

• 当 $0\le x\le 2k$ 时，$c\in [0,x]$，共 $x+1$ 对；
• 当 $2k<x\le 3k$ 时，$c\in [x-2k,2k]$，共 $4k-x+1$ 对。
  $f(p^k)={\sum }_{x=0}^{2k}(x+1)p^{3k-x}+{\sum }_{x=2k+1}^{3k}(4k-x+1)p^{3k-x}$

对于 $h_1(p^k)$（满足 $C=B$）：
此时 $c=k$。代入约束得 $e\le 2k$，此时 $D=p^{2k-e}$。
$h_1(p^k)={\sum }_{e=0}^{2k}{p}^{2k-e}$

对于 $h_3(p^k)$（满足 $C=E$）：
此时 $c=e$。代入约束得 $2c\le 3k⟹c\le \lfloor \frac{3k}{2}\rfloor$，此时 $D=p^{3k-2c}$。
$h_3(p^k)={\sum }_{c=0}^{\lfloor 3k/2\rfloor }{p}^{3k-2c}$

对于 $h_4(p^k)$（满足 $CE=B^2$）：
此时 $c+e=2k$，即 $x=2k$。代入得 $D=p^k$ 为常数。满足条件的 $(c,e)$ 有 $2k+1$ 对。
$h_4(p^k)=(2k+1)p^k$

对于 $h_5(p^k)$（满足 $C^{2}E=B^3$）：
此时 $2c+e=3k⟹e=3k-2c$。由于 $0\le e\le 2k$，解得 $\lceil \frac{k}{2}\rceil \le c\le \lfloor \frac{3k}{2}\rfloor$。此时 $D=p^{3k-(c+e)}=p^c$。
$h_5(p^k)={\sum }_{c=\lceil k/2\rceil }^{\lfloor 3k/2\rfloor }{p}^c$

欧拉线性筛

在明确了积性函数的局部公式后，可以利用欧拉线性筛（Euler Sieve）在 $O(n)$ 时间内预处理出所有 $1\dots n$ 的 $f$ 和 $h_i$。

算法流程如下：

1. 维护一个数组 low[i]，记录 $i$ 的最小质因子的纯次幂部分（如 $i=12=2^2\times 3$ 时，low[12] = 4）。
2. 在筛过程中，遇到质数 $p$ 时，直接代入 $k=1$ 计算 $f(p)$ 和 $h_i(p)$。
3. 当枚举到合数 $i\times p$ 时（$p$ 是 $i\times p$ 的最小质因子）：
   • 若 $i\mathrm{mod}p\ne 0$： $i$ 与 $p$ 互质，直接由积性函数性质得到 $f(i\times p)=f(i)\times f(p)$，low 更新为 low[i * p] = p。
   • 若 $i\mathrm{mod}p=0$： 此时 $p$ 是 $i$ 的因子。更新 low[i * p] = low[i] * p。
     • 若 low[i * p] == i * p，说明 $i\times p$ 整体是某个质数 $p$ 的纯次幂 $p^k$，此时暴力调用上面推导的公式进行 $O(k)$ 计算。
     • 若 low[i * p] != i * p，说明 $i\times p$ 可以拆分为互质的两部分：low[i * p] 和 (i * p) / low[i * p]。再次利用积性函数性质相乘得出结果。

通过该优化，空间复杂度为 $O(n)$，时间复杂度由于所有公式的累加计算均落在质数纯次幂点上，整体复杂度严格为 $O(n)$，完全可以在时限内通过 $10^7$ 的数据规模。最后基于计算出的数组，对于给定的 op，应用前文对应的求和/容斥公式即可输出答案。