bzoj4816/sdoi 2017 数字表格（莫比乌斯函数

分析

记 $f\left(i\right)$f(i) 为 $Fibonacci$Fibonacci 数列的第 $i$i 项
题目本质上要求
$ans={\prod }_{i=1}^n{\prod }_{j=1}^{m}f\left(gcd\right(i,j\left)\right)$ans=i=1∏n​j=1∏m​f(gcd(i,j))
枚举 $d=gcd(i,j)$d=gcd(i,j)
$ans={\prod }_{d=1}^{n}f(d{)}^{{\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==d]}$ans=d=1∏n​f(d)i=1∑n​j=1∑m​[gcd(i,j)==d]
对于右上角那部分，老生常谈了。
化简后要求的即是
$ans={\prod }_{d=1}^{n}f(d{)}^{{\sum }_{x=1}^{\lfloor {\displaystyle \frac{n}{d}}\rfloor }\mu \left(x\right)\lfloor {\displaystyle \frac{n}{dx}}\rfloor \lfloor {\displaystyle \frac{m}{dx}}\rfloor }$ans=d=1∏n​f(d)x=1∑⌊dn​⌋​μ(x)⌊dxn​⌋⌊dxm​⌋
然后套路枚举 $d$d 与 $x$x 的乘积
$ans={\prod }_{T=1}^n\prod _{d\mid T}f(d{)}^{\mu \left({\displaystyle \frac{T}{d}}\right)\lfloor {\displaystyle \frac{m}{T}}\rfloor \lfloor {\displaystyle \frac{m}{T}}\rfloor }$ans=T=1∏n​d∣T∏​f(d)μ(dT​)⌊Tm​⌋⌊Tm​⌋
预处理 $h\left(T\right)=\prod _{d\mid T}f(d{)}^{\mu \left({\displaystyle \frac{T}{d}}\right)}$h(T)=d∣T∏​f(d)μ(dT​) 及其前缀积即可。每次询问分块+快速幂即可。
特别一提的是，当 $\mu$μ 为 $-1$−1 时，乘上的应是 $f\left(d\right)$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;
}