谷外题题解

· · 个人记录

题面：给定 n,m,k \leq 10^9。考虑对于一个 n \times m 的矩形的每个格子填上 1 到 k 的一种颜色，并用这种图案填满一堵无限的墙，如果将平移相同的墙视作同一种情况，求总填色数。

首先，可以一眼看出这个是个 Polya 定理的题，重点在于考虑一个特定的平移情况的联通块数量。注意到所有的联通块显然是平移相同的，因此只需要考察一个联通块的点数量，就可以得到总数量。考虑对于平移 (a,b)，计算其需要从原点开始反复平移之后回到原点的最小步数，显然就是一个联通块的大小。设该值为 k，有方程：

n|ak, m|bk

可以发现有：

\frac{n}{(a,n)}|k, \frac{m}{(b,m)}|k

因此可以得到：

k=lcm(\frac{n}{(a,n)},\frac{m}{(b,m)})

设 i=\frac{n}{(a,n)},j=\frac{m}{(a,m)}，可以得到最后结果为：

\frac{1}{nm}\sum_{i|n,j|m} \varphi(i)\varphi(j)k^{nm/lcm(i,j)}

注意到小于 10^9 的因子个数最多为 1000 左右，直接预处理出所有的因子及其 \varphi(x)之后枚举即可。