P5221 Product

P5221 Product

求\(\prod_{i=1}^N\prod_{j=1}^N\frac{lcm(i,j)}{gcd(i,j)}\ (\bmod\ 104857601)\)
如果是上下同时除gcd的话会发现有点困难，但是如果上下同时乘一个gcd，会发现上面变得非常简单。

我们要求的就是分母
\(\prod_{i=1}^N\prod_{j=1}^N{(i,j)^2} (\bmod\ 104857601)\)
直接枚举gcd
\(\prod_{d=1}d^{\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}[(i,j)=1]}\)
可以直接套一个莫反或者转化用仪仗队的做法，反正算d的次方都得带个log。

#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
//#define A puts("Yes")
//#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
const ll mo1=1e9+7;
const ll mo2=1e9+9;
const ll P=131;
const ll Q=13331;
const ll inf=1e9;
const int N=1e6+5;
const ll mo=104857601;
ll n;
int p[N],tot,mu[N];
ll s[N];
bool vis[N];
ll power(ll a,ll b){
	ll t=1,y=a%mo;
	while (b) {
		if (b&1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}
ll gcd(ll a,ll b){
	if (!b) return a;
	return gcd(b,a%b);
}
int main() {
//    freopen("data.in", "r", stdin);
//    freopen("data.out", "w", stdout);

	scanf("%lld",&n);
	
	mu[1]=1;
	fo(i,2,n) {
		if (!vis[i]) {
			p[++tot]=i;
			mu[i]=-1;
		}
		fo(j,1,tot) {
			if (i*p[j]>=N) break;
			vis[i*p[j]]=1;
			if (i%p[j]==0) break;
			mu[i*p[j]]=-mu[i];
		}
	}
	fo(i,1,n) s[i]=s[i-1]+mu[i];

	ll fac=1;
	fo(i,1,n) fac=fac*i%mo;
	fac=power(fac,2*n)%mo;
	
	ll ans=1;
	for (ll lk=1,rk;lk<=n;lk=rk+1) {
		rk=n/(n/lk);
		ll t=0,z=n/lk,f;
		for (ll ld=1,rd;ld<=z;ld=rd+1) {
			rd=z/(z/ld);
			f=(s[rd]-s[ld-1])*(z/ld)*(z/ld);
			t+=f;
		}
		fo(i,lk,rk) ans=ans*power(i,t)%mo;
	}
	
	ans=ans*ans%mo;
	fac=fac*power(ans,mo-2)%mo;
	printf("%lld",fac);
//	printf("%lld\n",ans*ans%mo);
	
	
	
	
    return 0;
    


}

总结，有的时候约分并不一定会变得更加简单，可以观察一下乘上某个数能不能直接求出分子或分母。