T1 P1173 [NOI2016] 网格
T2 P1587 [NOI2016] 循环之美
考场切啦！虽然考场交的代码洛谷上TLE了一个点。
类比十进制，答案为
\[f(n,m,k)=\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=1][(j,k)=1]
\]
经过一些变形可得
\[f(n,m,k)=\sum_{d|k}\mu(d)f(\frac{m}{d},n,d)
\]
\[f(n, m, 1) = \sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=1]
\]
\[=\sum_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
\]
杜教筛+整除分块可以解决。