题目是这个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