SDOI2017 数字表格


Description

Doris 刚刚学习了 fibonacci 数列,用 \(f[i]\) 表示数列的第 \(i\) 项,那么: \[ \begin{aligned} &f[0]=0 \\ &f[1]=1 \\ &f[n] = f[n-1]+f[n-2] ,n \ge 2 \end{aligned} \]

Doris 用老师的超级计算机生成了一个 \(n \times m\) 的表格,第 \(i\) 行第 \(j\) 列的格子中的数是 \(f[\gcd(i,j)]\) ,其中 \(\gcd(i,j)\) 表示 \(i\)\(j\) 的最大公约数。

Doris 的表格中共有 \(n \times m\) 个数,她想知道这些数的乘积是多少。

这些数的乘积实在是太大了,所以 Doris 只想知道乘积对 \(1000000007\) 取模后的结果。

输入共 \(1 \le T \le 1000\) 组,每组有 \(1 \le n,m \le 10^6\)

Solution

即,求 \(\prod_{i=1}^{n}\prod_{j=1}^{m}f[gcd(i,j)]\)

\[ \begin{aligned} &\prod_{i=1}^{n}\prod_{j=1}^{m}f[gcd(i,j)] \\ &=\prod_{g=1}^{n}f[g]^{\sum_{i=1}^{n}\sum_{j=1}^{m}\left[\gcd[i,j]=g\right]}\\ &=\prod_{g=1}^{n} f[g]^{\sum_{i=1}^{\frac{n}{g}}\sum_{j=1}^{\frac{m}{g}}\left[\gcd[i,j]=1\right]} \\ &=\prod_{g=1}^{n} f[g]^{\sum_{i=1}^{\frac{n}{g}}\sum_{j=1}^{\frac{m}{g}}\sum_{d\mid\gcd[i,j]}\mu(d)} \\ &=\prod_{g=1}^{n} f[g]^{\sum_{d=1}^{\frac{n}{g}} \sum_{i=1}^{\frac{n}{gd}}\sum_{j=1}^{\frac{m}{gd}} \mu(d)} \\ &=\prod_{g=1}^{n} f[g]^{\sum_{d=1}^{\frac{n}{g}}\frac{n}{gd}\frac{m}{gd}\mu(d)} \\ \end{aligned} \]

Code


文章作者: ffacs
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ffacs !
  目录