萌新求助莫比乌斯反演

题目是这个blog里面的练习2
求

\prod_{i=1}^n\prod_{j=1}^m f_{\gcd(i,j)} (n,m \leq 10^6,T\leq 1000 )

其中

T

为数据组数，

f

为斐波那契数列

以下是蒟蒻的推导：

原式

=\prod_{d=1}^nf_d^{\sum^n_{i=1}\sum^m_{j=1}[\gcd(i,j)=d]}

=\prod_{d=1}^nf_d^{\sum^{\lfloor \frac{n}{d} \rfloor}_{i=1}\sum^{\lfloor \frac{m}{d} \rfloor}_{j=1}[\gcd(i,j)=1]}

=\prod_{d=1}^nf_d^{\sum^{\lfloor \frac{n}{d} \rfloor}_{i=1}\sum^{\lfloor \frac{m}{d} \rfloor}_{j=1}\sum_{k|\gcd(i,j)}\mu(k)}

=\prod_{d=1}^nf_d^{\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\cdot \mu(k)\cdot \lfloor \frac{n}{dk}\rfloor \cdot \lfloor \frac{m}{dk}\rfloor}

此时已经存在

O(\sqrt n \cdot \sqrt n)= O(n)

的做法了，设

T=dk

，

g(x)=\lfloor\frac{x}{T}\rfloor

，则原式可化为

\prod^n_{T=1}(\prod_{d|T}f_d^{\mu(\frac{T}{d})})^{g(n) \cdot g(m)}

设

F(T)=\prod_{d|T}f_d^{\mu(\frac{T}{d})}

，按照博客的前文所述，如果能够快速高效地求出

F

，则可以在

O(\sqrt n)

的复杂度内处理每一个询问，但蒟蒻推导+打表之后并没有发现任何可以利用的性质，求大佬解答，谢谢 QAQ

讨论操作