Luogu P4917 天守阁的地板

jszjinshengzhi · 2018-10-17 19:58:27 · 题解

Luogu P4917 天守阁的地板

题意：给定n，求用a\times b(1\le a,b\le n)的木板铺出一个最小的正方形所消耗木板的数量。为了避免高精，只用求范围内所有的a,b对应的答案的积（答案对长者生日19260817）。

数据范围：多组数据，T\le1000,n\le1000000

分析：对于a\times b的木板，能铺成的最小正方形的边长为lcm(a,b)，所用木板数即为\frac{lcm(a,b)^2}{a\cdot b}

所以 Ans=\prod_{a=1}^n\prod_{b=1}^n\frac{lcm(a,b)^2}{a\cdot b}

接下来就是暴力推柿子了。

看着lcm就特别不爽，于是把它换成gcd。

注意到lcm(a,b)=\frac{a\cdot b}{gcd(a,b)}，代入，有Ans=\prod_{a=1}^n\prod_{b=1}^n\frac{a\cdot b}{gcd(a,b)^2}

直接把分数化开来推想想都觉得很麻烦，而分子部分只有a,b两个字母，求积就是个阶乘的2n次幂，分母gcd又有很多现成的套路，看着多舒服，干脆直接把分子分母拆开来算。

分子=(n!)^{2\cdot n}

分母=\prod_{a=1}^n\prod_{b=1}^ngcd(a,b)^2=(\prod_{d=1}^nd^{\sum_{a=1}^{\lfloor\frac nd\rfloor}\sum_{b=1}^{\lfloor\frac nd\rfloor}gcd(a,b)==1})^2\qquad（枚举gcd）

分母中的n!提到分子，就可以开始开心的整除分块了，只需O(n)预处理筛出\varphi的前缀和、阶乘、逆元即可。

复杂度：O(T\cdot\sqrt n)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define p 19260817

inline ll fpow(ll a,ll b){
    ll ret=1;
    for(;b;ret*=((b&1)?a:1),ret%=p,a=a*a%p,b>>=1);
    return ret;
}

#define maxn 1000005
ll phi[maxn],fac[maxn];
ll cnt,prime[maxn];
inline void init(){
    phi[1]=1;
    for(ll i=2;i<maxn;++i){
        if(!phi[i]){
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(ll j=1;j<=cnt&&prime[j]*i<maxn;++j){
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
    fac[0]=1;
    for(ll i=1;i<maxn;++i){
        phi[i]=(phi[i]+phi[i-1])%(p-1);//！！！这里模的是p-1，因为phi出现在指数中！！！ 
        fac[i]=fac[i-1]*i%p;
    }
}

int T;
ll n,ans;
int main(){
    init();
    scanf("%d",&T);
    while(T--){
        scanf("%lld",&n);
        ans=1;
        for(ll l=1,r;l<=n;l=r+1){
            r=n/(n/l);
            ans=ans*fpow(fac[r]*fpow(fac[l-1],p-2)%p,phi[n/l])%p;
        }
        printf("%lld\n",fpow(fac[n],2*n+2)*fpow(ans,p-5)%p);//这里的fpow(ans,p-5)表示ans^4的逆元
    }
    return 0;
}