(\)
(Description)
定义二元函数(F(x,y))表示，用 (x imes y) 的矩形不可旋转的铺成一个任意边长的正方形，所需要的最少的矩形个数。
现在(T)组询问，每次给出一个(N)，求(prod_{i=1}^Nprod_{j=1}^N F(i,j)) 模(19260817)的值。
- (Nin[1,10^6],Tin[1,10^3])
(\)
下面的表述中用([x,y])表示(Lcm(x,y))，用((x,y))表示(Gcd(x,y))。
(\)
(Solution1: ext O(N+Tsqrt NlogN))
出题人的做法。对于(N)更大一些，(T)较小的情况表现比较优秀。
考虑一个边长为(x imes y)的矩形铺成的最小正方形的边长，因为不可旋转，所以答案为([x,y])。
那么用这种矩形铺出这个正方形需要的块数就是(frac{[x,y]^2}{xy})，总面积除以单块面积嘛。
然后所求可以形式化的写出：
上面的转化是基于以下定理：
然后考虑对于每一次询问的(N)，如何快速求出答案。
(\)
首先将分母分子分开考虑，对于分子，有：
具体证明不太好说，大致是每一次循环到的(i)都要被乘上(N)次，手玩一下差不多就懂了。
这部分显然可以( ext O(N))求(N!)，然后再每一个数都算一个快速幂即可，预处理复杂度( ext O(Nlog(2N)))。
(\)
然后考虑分子部分如何求，首先先将平方提出来：
因为是连乘显然合理。
然后括号里的东西显然可以根据(Gcd)的值分情况讨论：
然后根据仪仗队的解法，我们知道有：
然后可以线性筛求(varphi)，预处理(varphi)的前缀和，查询这个指数就是( ext O(1))的了，预处理复杂度( ext O(N))。
我们设(g[x])表示：
那么现在需要解决的式子是
然后注意到这个东西可以除法分块，考虑对于一个(lfloorfrac Nd floor)相同的区间([L,R])，答案为
然后连乘积部分可以用阶乘相除的方法求解，因为模意义下我们还需要处理每一个阶乘的逆元。
然后快速幂求一下，在套回去平方一下，再求个逆元乘上((N !)^{2N})就是答案了。
单次处理除法分块+快速幂复杂度( ext O(sqrt NlogN))，总复杂度( ext O(N+Tsqrt NlogN))
(\)
(Code1： ext O(N+Tsqrt NlogN))
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define gc getchar
#define N 1000010
#define mod 19260817ll
using namespace std;
typedef long long ll;
ll g[N]={1,1},phi[N]={0,1},prm[N];
ll fac[N]={0,1},fac2[N]={0,1},inv[N]={1};
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline ll qpow(ll x,ll t){
ll res=1ll;
while(t){
if(t&1) (res*=x)%=mod;
(x*=x)%=mod; t>>=1;
}
return res;
}
inline void init(){
for(R int i=2;i<N;++i){
g[i]=1;
if(!phi[i]){phi[i]=i-1;prm[++prm[0]]=i;}
for(R int j=1,k;j<=prm[0]&&(k=prm[j]*i)<N;++j)
if(i%prm[j]) phi[k]=phi[i]*phi[prm[j]];
else{phi[k]=phi[i]*prm[j];break;}
}
for(R ll i=2;i<N;++i) fac[i]=fac[i-1]*i%mod,phi[i]+=phi[i-1];
for(R int i=2;i<N;++i) fac2[i]=qpow(fac[i],(i<<1));
for(R int i=1;i<N;++i) inv[i]=qpow(fac[i],mod-2);
}
inline void work(){
ll n=rd(),ans=1ll;
for(R ll l=1,t,r;l<=n;l=r+1){
t=n/l; r=n/t;
(ans*=qpow(fac[r]*inv[l-1]%mod,phi[t]*2-1))%=mod;
}
ans=(qpow(ans,(mod-2)<<1)*fac2[n])%mod;
printf("%lld
",ans);
}
int main(){
init();
int t=rd();
while(t--) work();
return 0;
}
(\)
(Solution2: ext O(Nsqrt NlogN+T))
我的做法。卡着时限也就过了，对(T)大的时候表现会很优秀。
继续考虑这个式子：
分子部分不变，还是那么预处理，分母我有一个不同的做法。
首先还是把平方套在外面：
然后平方里面的部分解法就不太一样了，设一个(g[n])表示：
第一个等号是定义，第二个等号理解为，设((i,n)=d)，那么这样的数对有(varphi(lfloorfrac{N}{d} floor))个，因为除掉(d)两数应该互质。
然后类似仪仗队的做法，把求和扩展到求积，那么考虑将下三角矩阵的积求出来，答案是
然后整个矩阵的积是下三角的平方除以对角线，对角线的积是(prod(i,i)=N !)，所以整个矩阵的积等于
回到所求，有
复杂度预处理 (g) 数组( ext O(Nsqrt NlogN))，分别代表质因数分解和快速幂的复杂度。
其他线性筛、求阶乘、求逆元等的复杂度都不会太高，之后显然每一个数的答案都可以( ext O(1))得到了。
(\)
(Code2： ext O(Nsqrt NlogN+T))
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define gc getchar
#define N 1000010
#define mod 19260817ll
using namespace std;
typedef long long ll;
ll g[N]={1},fac[N]={0,1};
int phi[N]={0,1},prm[N];
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline ll qpow(ll x,ll t){
ll res=1ll;
while(t){
if(t&1) (res*=x)%=mod;
(x*=x)%=mod; t>>=1;
}
return res;
}
inline void init(){
for(R int i=2;i<N;++i){
if(!phi[i]){phi[i]=i-1;prm[++prm[0]]=i;}
for(R int j=1,k;j<=prm[0]&&(k=prm[j]*i)<N;++j)
if(i%prm[j]) phi[k]=phi[i]*phi[prm[j]];
else{phi[k]=phi[i]*prm[j];break;}
}
for(R ll i=2;i<N;++i) fac[i]=fac[i-1]*i%mod;
for(R int i=2;i<N;++i) fac[i]=qpow(fac[i],(i<<1)+2);
for(R int i=1,r;i<N;++i){
r=sqrt(i); g[i]=1ll;
for(R int j=1;j<=r;++j)
if(i%j==0){
(g[i]*=qpow(j,phi[i/j]))%=mod;
if(i/j!=j) (g[i]*=qpow(i/j,phi[j]))%=mod;
}
(g[i]*=g[i-1])%=mod;
}
for(R int i=1;i<N;++i) g[i]=qpow(g[i],(mod-2)*4);
for(R int i=1;i<N;++i) (g[i]*=fac[i])%=mod;
}
int main(){
init();
int t=rd();
while(t--) printf("%lld
",g[rd()]);
return 0;
}
(\)
(Solution3: ext O(N imes lnN imes logN+T))
优化一下第二个做法。
依次考虑每一个数对每一个 (g) 的贡献，所以一个数 (i) 能做贡献的数有(lfloorfrac Ni floor)个，直接暴力乘更新 (g) 就好。
此时复杂度神奇的降到了调和级数，也就是(ln N)。
(\)
(Code3: ext O(N imes lnN imes logN+T))
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define gc getchar
#define N 1000010
#define mod 19260817ll
using namespace std;
typedef long long ll;
ll g[N]={1,1},fac[N]={0,1};
int phi[N]={0,1},prm[N];
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline ll qpow(ll x,ll t){
ll res=1ll;
while(t){
if(t&1) (res*=x)%=mod;
(x*=x)%=mod; t>>=1;
}
return res;
}
inline void init(){
for(R int i=2;i<N;++i){
g[i]=1;
if(!phi[i]){phi[i]=i-1;prm[++prm[0]]=i;}
for(R int j=1,k;j<=prm[0]&&(k=prm[j]*i)<N;++j)
if(i%prm[j]) phi[k]=phi[i]*phi[prm[j]];
else{phi[k]=phi[i]*prm[j];break;}
}
for(R ll i=2;i<N;++i) fac[i]=fac[i-1]*i%mod;
for(R int i=2;i<N;++i) fac[i]=qpow(fac[i],(i<<1)+2);
for(R int i=1;i<N;++i)
for(R ll j=1;j*(ll)i<(ll)N;++j) (g[j*i]*=qpow(i,phi[j]))%=mod;
for(R int i=1;i<N;++i) (g[i]*=g[i-1])%=mod;
for(R int i=1;i<N;++i) g[i]=qpow(g[i],(mod-2)*4);
for(R int i=1;i<N;++i) (g[i]*=fac[i])%=mod;
}
int main(){
init();
int t=rd();
while(t--) printf("%lld
",g[rd()]);
return 0;
}