题目大意：有$T(Tleqslant 1000)$组数据，每组数据给你$n,m(1leqslant n,m leqslant 10^6)$，求出$displaystyleprodlimits_{i=1}^n displaystyleprodlimits_{j=1}^m F[(i,j)]$（$F(i)$为$fibonacci$数列第$i$项）
题解：下文中假设$n leqslant m$
$$
defdprod{displaystyleprodlimits}\
defdsum{displaystylesumlimits}\
dprod_{i=1}^ndprod_{j=1}^m F[(i,j)]=dprod_{d=1}^n F(d)^{sum_{i=1}^nsum_{j=1}^m [(i,j)==d]}\
令g(p)=dsum_{i=1}^ndsum_{j=1}^m [(i,j)==p]\
egin{align*}
令G(p)&=dsum_{p|k}g(k)\
&=dsum_{p|k}dsum_{i=1}^ndsum_{j=1}^m [(i,j)==k]\
&=dsum_{i=1}^ndsum_{j=1}^m [p|(i,j)]\
&=leftlfloordfrac{n}{p}
ight
floorcdotleftlfloordfrac{m}{p}
ight
floor
end{align*}\
$$
$$
defdsum{displaystylesumlimits}\
莫比乌斯反演得：\
egin{align*}
g(p)&=dsum_{p|k}muig(dfrac{k}{p}ig)G(p)\
&=dsum_{p|k}muig(dfrac{k}{p}ig)leftlfloordfrac{n}{p}
ight
floorcdotleftlfloordfrac{m}{p}
ight
floor\
&=dsum_{i=1}^nmu(i)leftlfloordfrac{n}{icdot p}
ight
floorcdotleftlfloordfrac{m}{icdot p}
ight
floor
end{align*}
$$
$$
defdprod{displaystyleprodlimits}\
defdsum{displaystylesumlimits}\
egin{align*}
dprod_{i=1}^ndprod_{j=m}^m F[(i,j)]&=dprod_{d=1}^n F(d)^{sum_{i=1}^nsum_{j=1}^m [(i,j)==d]}\
&=dprod_{d=1}^nF(d)^{g(d)}\
&=dprod_{d=1}^nF(d)^{sum_{i=1}^nmu(i)lfloorfrac{n}{i p}
floorcdotlfloorfrac{m}{i p}
floor}\
&=dprod_{d=1}^ndprod_{d|k}F(d)^{muig(dfrac{k}{d}ig)iglfloordfrac{n}{k}ig
flooriglfloordfrac{m}{k}ig
floor}\
&=dprod_{k=1}^nigg(dprod_{d|k}F(d)^{muig(dfrac{k}{d}ig)}igg)^{iglfloordfrac{n}{k}ig
flooriglfloordfrac{m}{k}ig
floor}\
end{align*}\
$$
$$
defdprod{displaystyleprodlimits}\
令s[k]=dprod_{d|k}F(d)^{muig(dfrac{k}{d}ig)}\
预处理出s，然后整除分块就行了
$$
卡点：无
C++ Code：
#include <cstdio>
#include <cstring>
#define maxn 1000010
using namespace std;
const int mod = 1000000007;
int F[maxn], invF[maxn], s[maxn], invs[maxn];
int plist[maxn], miu[maxn], ptot;
bool isp[maxn];
int pw(int base, int p) {
base %= mod, p %= mod - 1;
int ans = 1;
for (; p; p >>= 1, base = 1ll * base * base % mod)
if (p & 1) ans = 1ll * ans * base % mod;
return ans;
}
int inv(int a) {
return pw(a, mod - 2);
}
void sieve(int n) {
invs[0] = s[0] = s[1] = 1;
F[0] = 0; invF[1] = F[1] = miu[1] = 1;
for (int i = 2; i < n; i++) {
s[i] = 1;
F[i] = (F[i - 1] + F[i - 2]) % mod;
invF[i] = inv(F[i]);
if(!isp[i]) plist[ptot++] = i, miu[i] = -1;
for (int j = 0; j < ptot && i * plist[j] < n; j++) {
int tmp = i * plist[j];
isp[tmp] = true;
if (i % plist[j] == 0) {
miu[tmp] = 0;
break;
}
miu[tmp] = -miu[i];
}
}
for (int i = 1; i < n; i++) {
for (int j = 1, k = i; k < n; j++, k += i) {
if (miu[j] == 1) s[k] = 1ll * s[k] * F[i] % mod;
if (miu[j] == -1) s[k] = 1ll * s[k] * invF[i] % mod;
}
}
for (int i = 1; i < n; i++) {
s[i] = 1ll * s[i] * s[i - 1] % mod;
invs[i] = inv(s[i]);
}
}
inline int min(int a, int b) {return a < b ? a : b;}
int solve(int n, int m) {
int tmp = min(n, m), ans = 1, j;
for (int i = 1; i <= tmp; i = j + 1) {
j = min(n / (n / i), m / (m / i));
ans = 1ll * ans * pw(1ll * s[j] * invs[i - 1] % mod, 1ll * (n / i) * (m / i) % (mod - 1)) % mod;
}
return ans;
}
int Tim, n, m;
int main() {
sieve(maxn);
scanf("%d", &Tim);
while (Tim --> 0) {
scanf("%d%d", &n, &m);
printf("%d
", solve(n, m));
}
return 0;
}