[Sdoi2017]数字表格

题意：求

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

考场60分

其实多推一步就推倒了...

因为是乘，我们可以放到幂上

\[\prod_{d=1}^n \prod_{i=1}^{\frac{n}{d}}\prod_{i=1}^{\frac{m}{d}} f[d]^{[(i,j)=1]}
\]

套路一直推完

\[\prod_{D=1}^n \prod_{d|D} f[d]^{\mu(\frac{D}{d}) \cdot \frac{n}{D} \cdot \frac{m}{D}}
\]

用枚举倍数的方法预处理

\[\prod_{d|D} f[d]^{\mu(\frac{D}{d})}
\]

的前缀积就行了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

using namespace std;

const int N=1e6+5, mo=1e9+7;

typedef long long ll;

inline int read() {

	char c=getchar(); int x=0, f=1;

	while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

	while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

	return x*f;

}

int Q, n, m, f[N]; ll g[N];

inline ll Pow(ll a, int b) {

	ll ans=1;

	for(; b; b>>=1, a=a*a%mo)

		if(b&1) ans=ans*a%mo;

	return ans;

}

int p[N], notp[N]; ll mu[N];

inline void mod(int &x) {if(x>=mo) x-=mo;}

inline void mod(ll &x) {if(x>=mo) x-=mo;}

void sieve(int n) {

	mu[1]=1;

	for(int i=2; i<=n; i++) { //printf("i %d\n",i);

		if(!notp[i]) p[++p[0]]=i, mu[i]=-1;

		for(int j=1; j<=p[0] && i*p[j]<=n; j++) { //printf("j %d\n",p[j]);

			notp[ i*p[j] ]=1;

			if(i % p[j] == 0) {

				mu[ i*p[j] ]=0;

				break;

			}

			mu[ i*p[j] ] = -mu[i];

		}

	}

	f[0]=0; f[1]=1; g[1]=1; g[0]=1;

	for(int i=2; i<=n; i++) mod(f[i] += f[i-1] + f[i-2]), g[i] = 1;

	for(int i=1; i<=n; i++) {

		ll inv = Pow(f[i], mo-2);

		for(int j=i, k=1; j<=n; j+=i, k++) if(mu[k]) ( g[j] *= (mu[k]==1 ? f[i] : inv) ) %= mo;

		(g[i] *= g[i-1]) %= mo;

	}

	//for(int i=1; i<=10; i++) printf("fg %d  %d  %lld\n", i, f[i], g[i]);

}

void cal(int n, int m) {

	if(n>m) swap(n, m);

	ll ans=1; int r;

	for(int i=1; i<=n; i=r+1) {

		r = min(n/(n/i), m/(m/i));

		( ans *= Pow(g[r] * Pow(g[i-1], mo-2) %mo, (ll)(n/i) * (m/i) % (mo-1)) ) %= mo;

	}

	printf("%lld\n", ans);

}

int main() {

	freopen("product.in", "r", stdin);

	freopen("product.out", "w", stdout);

	sieve(N-1);

	Q=read();

	for(int i=1; i<=Q; i++) {

		n=read(); m=read();

		cal(n, m);

	}

}

巴特西

[Sdoi2017]数字表格 [莫比乌斯反演]

[Sdoi2017]数字表格

最新文章

热门文章