我不会数学1

定义 λ(x)=[\rm x \ is\ a \ fibonacci \ number] ，f(i) 为斐波那契数列第 i 项，其中 f(0)=0,f(1)=1，则

\large \prod_{x=1}^{\infty} x^{\sum ^{\lfloor \frac {f(n)}x\rfloor}_{p=1} λ(px) \sum ^{\lfloor \frac {f(m)}x\rfloor}_{q=1}λ(qx)\ [\gcd(p,q)=1]}

是多少（其中多组询问 T\leq1000,n,m\leq 10^6 ）。

只有我不知道的斐波那契性质：

n|m \to f(n)|f(m)

\gcd (f(i),f(j)) = f(\gcd(i,j)) \ \ \ (2)

(2) 可由

f(n)=f(m)\times f(n-m+1) +f(m-1)\times f(n-m)\ \ \ (3)

推出， (3) 直接暴力分解即可得。

直接考虑 f(i) , f(j) 对答案的贡献为

\prod_{x|f(i),x|f(j)} x \times [\gcd(\frac{f(i)}x,\frac{f(j)}x)=1]

=\prod_{x|\gcd(f(i),f(j))}x \times [\frac{\gcd(f(i),f(j))}x =1]

=\gcd(f(i),f(j))=f(\gcd(i,j))

则原式等于

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

\large=\prod _{d=1}^{\min(n,m)}\prod_{i=1}^n \prod_{j=1}^m f(d)^{[\gcd(i,j)=d]}

\large =\prod _{d=1}^{\min(n,m)} f(d)^{\sum _{i=1}^{ \lfloor\frac n d \rfloor} \sum_{j=1}^{ \lfloor \frac m d \rfloor}[\gcd(i,j)=1]}

\large =\prod _{d=1}^{\min(n,m)} f(d)^{\sum _{i=1}^{ \lfloor\frac n d \rfloor} \sum_{j=1}^{ \lfloor \frac m d \rfloor} \sum_{D|i,D|j} \mu(D)}

=\large \prod _{d=1}^{\min(n,m)} f(d) ^{\sum _{D=1} \mu(D) \lfloor \frac m {Dd}\rfloor \lfloor \frac n {Dd}\rfloor}

\large =\prod _{d=1}^{\min(n,m)} \prod _{D=1}f(d)^{\mu(D) \lfloor \frac m {Dd}\rfloor \lfloor \frac n {Dd}\rfloor}

=\large \prod_{E=1}^{\min(n,m)} (\prod _{D|E} f(\frac ED)^{\mu(D)})^{\lfloor \frac n E \rfloor \lfloor \frac m E \rfloor }

中间括号里的东西只和 E 有关，预处理一下是 O(n\log n) 的，再对整个东西整除搞整除分块（快速幂是 \log），整体是 O(n\log n+ T\sqrt n \log n) 。