分析
记 f(i) 为 Fibonacci 数列的第 i 项
题目本质上要求
ans=i=1∏nj=1∏mf(gcd(i,j))
枚举 d=gcd(i,j)
ans=d=1∏nf(d)i=1∑nj=1∑m[gcd(i,j)==d]
对于右上角那部分,老生常谈了。
化简后要求的即是
ans=d=1∏nf(d)x=1∑⌊dn⌋μ(x)⌊dxn⌋⌊dxm⌋
然后套路枚举 d 与 x 的乘积
ans=T=1∏nd∣T∏f(d)μ(dT)⌊Tm⌋⌊Tm⌋
预处理 h(T)=d∣T∏f(d)μ(dT) 及其前缀积即可。每次询问分块+快速幂即可。
特别一提的是,当 μ 为 −1 时,乘上的应是 f(d) 的逆元。
代码如下
#include <bits/stdc++.h>
#define mod 1000000007
#define N 1000007
#define LL long long
using namespace std;
LL z = 1;
int f[N], mu[N], x[N], p[N], g[N], s[N], inv[N], cnt, maxn = N - 7;
LL t;
int ksm(int a, int b, int p){
int s = 1;
while(b){
if(b & 1) s = z * s * a % mod;
a = z * a * a % mod;
b >>= 1;
}
return s;
}
int main(){
int i, j, n, m, T, l, r, ji, ans;
inv[1] = 1;
for(i = 2; i <= maxn; i++){
inv[i] = z * (mod - mod / i) * inv[mod % i] % mod;
}
mu[1] = 1;
for(i = 2; i <= maxn; i++){
if(!x[i]) x[i] = i,p[++cnt] = i, mu[i] = -1;
for(j = 1; j <= cnt; j++){
t = z * i * p[j];
if(t > maxn) break;
x[t] = p[j];
if(i % p[j] == 0) break;
mu[t] = -mu[i];
}
}
f[1] = 1;
for(i = 2; i <= maxn; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
for(i = 0; i <= maxn; i++) g[i] = 1;
for(i = 1; i <= maxn; i++){
for(j = 1; z * i * j <= maxn; j++){
if(mu[j] == -1) g[i * j] = z * g[i * j] * ksm(f[i], mod - 2, mod) % mod;
if(mu[j] == 1) g[i * j] = z * g[i * j] * f[i] % mod;
}
}
s[0] = 1;
for(i = 1; i <= maxn; i++) s[i] = z * s[i - 1] * g[i] % mod;
scanf("%d", &T);
while(T--){
ans = 1;
scanf("%d%d", &n, &m);
if(n > m) swap(n, m);
for(l = 1; l <= n; l = r + 1){
r = min(n / (n / l), m / (m / l));
ji = z * s[r] * ksm(s[l - 1], mod - 2, mod) % mod;
ji =ksm(ji, n / l, mod);
ji = ksm(ji, m / l, mod);
ans = z * ans * ji % mod;
}
printf("%d\n", ans);
}
return 0;
}