洛咕
题意:给出\(A\),\(B\),求下面的式子的值.
\[\prod_{i=A}^{B}\prod_{j=1}^{i}(\frac{i}{j})^{\lfloor \frac{i}{j} \rfloor}\ (\bmod \ 19260817)\]
包含\(T\)组询问.\(A,B<=1e6.\)
分析:一道数学推式子的好题,所运用到的知识都在\(CSP\)范围内.
首先一个最基本的技巧就是将答案转化为前缀和相除的形式,即\(ans=sum[B]/sum[A-1]\),当然除以是乘上逆元..
然后设\(val[i]=\prod_{j=1}^{i}(\frac{i}{j})^{\lfloor \frac{i}{j} \rfloor}=\prod_{j=1}^{i}i^{\lfloor \frac{i}{j} \rfloor}*\prod_{j=1}^{i}inv[j]^{\lfloor \frac{i}{j} \rfloor}\).(\(inv[j^{\lfloor \frac{i}{j} \rfloor}]=inv[j]^{\lfloor \frac{i}{j} \rfloor}\))
显然,\(sum[i]=\prod_{j=1}^{i}val[j]\).
然后设\(A[i]=\prod_{j=1}^{i}i^{\lfloor \frac{i}{j} \rfloor},B[i]=\prod_{j=1}^{i}inv[j]^{\lfloor \frac{i}{j} \rfloor}\),考虑如何分别求这两个式子?
\(A[i]=\prod_{j=1}^{i}i^{\lfloor \frac{i}{j} \rfloor}=i^{\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor}\)(原理:\(x^y*x^z=x^{y+z}\)).
设\(C[i]=\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor\),则\(A[i]=i^{C[i]}.\)对于同一个\(j\)来说,\(\lfloor \frac{i}{j} \rfloor\)不等于\(\lfloor \frac{i+1}{j} \rfloor\),当且仅当\(j\)是\(i+1\)的约数.所以\(C[i]=C[i-1]+i\)的约数个数.显然,\(1\)~\(N\)的每个数的约数个数可以用倍数法在\(NlogN\)内求解出来,且有结论个数总和大约为\(NlogN\).至此,\(A[i]\)已经可以求出来了.
\(B[i]\)的结论与\(A[i]\)类似,我是通过手列了几项得出来的.
\(B[1]=inv[1]^1\)
\(B[2]=inv[1]^2*inv[2]^1\)
\(B[3]=inv[1]^3*inv[2]^1*inv[3]^1\)
\(B[4]=inv[1]^4*inv[2]^2*inv[3]^1*inv[4]^1\)
可以发现\(B[i]\)在\(B[i-1]\)的基础上,乘上了是其约数的项.例如\(4\)的约数有\(1,2,4\),所以\(B[4]=B[3]*inv[1]*inv[2]*inv[4]\).
至此,主要原理都讲完了.有一个细节就是本题卡空间,倍数法求每个数的约数集合时,不要开\(vector\)记录,而是直接更新要更新的数组即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int mod=19260817;
const int N=1e6+5;
ll A[N],B[N],C[N],inv[N],val[N],sum[N];
inline ll ksm(ll a,ll b){
ll cnt=1;
while(b){
if(b&1)cnt=(1ll*cnt*a)%mod;
a=(1ll*a*a)%mod;
b>>=1;
}
return cnt;
}
int main(){
inv[1]=1;
for(int i=2;i<=N-5;++i)
inv[i]=(1ll*(mod-mod/i)*inv[mod%i])%mod;//线性推1到N的逆元
for(int i=1;i<=N-5;++i)B[i]=1;//初始化,乘积为1
for(int i=1;i<=N-5;++i){//倍数法求约数集合
int j=1;
for(j=1;i*j<=N-5;++j){//直接更新数组,不要用vector记录
B[i*j]=(1ll*B[i*j]*inv[i])%mod;//i是i*j的约数之一
++C[i*j];//i*j这个数的约数个数加1
}
}
for(int i=2;i<=N-5;++i)B[i]=(1ll*B[i]*B[i-1])%mod;
//倍数法过后,B[i]只是其所有约数的逆元的乘积,例如B[4]=inv[1]*inv[2]*inv[4]
//所以根据上面的分析,还要乘上前面一项.
for(int i=2;i<=N-5;++i)C[i]+=C[i-1];
//C数组同理,在倍数法过后,C[i]=i的约数个数,还要加上前面一项的值.
for(int i=1;i<=N-5;++i)A[i]=ksm(i,C[i]);
for(int i=1;i<=N-5;++i)val[i]=(1ll*A[i]*B[i])%mod;
sum[1]=val[1];for(int i=2;i<=N-5;++i)sum[i]=(1ll*sum[i-1]*val[i])%mod;
int T=read();
while(T--){
int a=read(),b=read();
if(a>1)printf("%lld\n",sum[b]*ksm(sum[a-1],mod-2)%mod);//防止a-1=0的情况
else printf("%lld\n",sum[b]);
}
return 0;
}