loj2000 「SDOI2017」数字表格

there
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long ll;

int T, n, m, pri[1000005], pricnt, mu[1000005], f[1000005], g[1000005], F[1000005];

bool isp[1000005];

const int mod=1000000007;

template <typename _T> int ksm(int a, _T b){

	int re=1;

	while(b){

		if(b&1)	re = (ll)re * a % mod;

		a = (ll)a * a % mod;

		b >>= 1;

	}

	return re;

}

void shai(){

	memset(isp, true, sizeof(isp));

	isp[0] = isp[1] = false;

	mu[1] = 1;

	for(int i=2; i<=1000000; i++){

		if(isp[i])	pri[++pricnt] = i, mu[i] = -1;

		for(int j=1; j<=pricnt && (ll)i*pri[j]<=1000000; j++){

			isp[i*pri[j]] = false;

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

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

				break;

			}

			else	mu[pri[j]*i] = -mu[i];

		}

	}

	f[0] = 0;

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

	for(int i=2; i<=1000000; i++){

		f[i] = (f[i-1] + f[i-2]) % mod;

		g[i] = ksm(f[i], mod-2);

		F[i] = 1;

	}

	for(int i=1; i<=1000000; i++)

		if(mu[i]!=0)

			for(int j=i; j<=1000000; j+=i)

				F[j] = (ll)F[j] * (mu[i]>0?f[j/i]:g[j/i]) % mod;

	for(int i=1; i<=1000000; i++)

		F[i] = (ll)F[i-1] * F[i] % mod;

}

int calc(int n, int m){

	int re=1;

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

		int nxt=min(n/(n/i), m/(m/i));

		int tmp1=(ll)F[nxt]*ksm(F[i-1], mod-2)%mod;

		int faq=ksm(tmp1, (ll)(n/i)*(m/i));

		re = (ll)re * faq % mod;

		i = nxt + 1;

	}

	return re;

}

int main(){

	cin>>T;

	shai();

	while(T--){

		scanf("%d %d", &n, &m);

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

		printf("%d\n", calc(n, m));

	}

	return 0;

}
巴特西

loj2000 「SDOI2017」数字表格

最新文章

热门文章
