版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [Luogu P3704] [SDOI2017] 数字表格" categories:
Doris 刚刚学习了 fibonacci 数列. 用 $f_i$ 表示数列的第 $i$ 项, 那么
$$ f_0=0,f_1=1 $$
$$ fn=f{n-1}+f_{n-2},n\geq 2 $$
Doris 用老师的超级计算机生成了一个 $n\times m$ 的表格, 第 $i$ 行第 $j$ 列的格子中的数是 $f_{\gcd(i,j)}$, 其中 $\gcd(i,j)$ 表示 $i,j$ 的最大公约数. Doris 的表格中共有 $n\times m$ 个数, 她想知道这些数的乘积是多少. 答案对 $10^9+7$ 取模
本题单个测试点内有多组测试数据. 输入的第一行是一个整数 $T$, 表示测试数据的组数. 接下来 $T$ 行, 每行两个整数 $n, m$, 表示一组数据
对于每组数据, 输出一行一个整数表示答案
3
2 3
4 5
6 7
1
6
960
数据规模与约定
推式子, 不妨设 $n\geqslant m$
$$ \begin{aligned} \prod{i=1}^n\prod{j=1}^mf{(i,j)}&=\prod{d=1}^n\prod{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod{j=1}^{\lfloor\frac{m}{d}\rfloor}fd^{[(i,j)=1]}\ &=\prod{d=1}^nfd^{\sum{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]}\ &=\prod{d=1}^nfd^{\sum{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum{e\mid (i,j)}\mu(e)}\ &=\prod_{d=1}^nfd^{\sum{e=1}^{\lfloor\frac{n}{d}\rfloor}\mu(e)\lfloor\frac{n}{de}\rfloor\lfloor\frac{m}{de}\rfloor}\ &\xlongequal{D=de}\prod{D=1}^n\bigg(\prod{d\mid D}f_d^{\mu(\frac{D}{d})}\bigg)^{\lfloor\frac{n}{D}\rfloor\lfloor\frac{m}{D}\rfloor} \end{aligned} $$
其中 $\prod_{d\mid D}f_d^{\mu(\frac{D}{d})}$ 部分可以 $O(n\log n)$ 求出, 之后就是整除分块了
$O(n\log n)$