乘积
给出\(A\),\(B\),求下面的式子的值.
\[\prod_{i=A}^{B}\prod_{j=1}^{i}(\frac{i}{j})^{\left\lfloor \frac{i}{j} \right\rfloor}\ (\bmod \ 19260817) \]包含\(T\)组询问.
\(T\le 10^6,A\le B\le10^6\)
解
下面叙述暂时不考虑取模，计算时取模即可。
转化为求：
设\(Ans(n)=\prod_{i=1}^n\prod_{j=1}^i(\frac{i}{j})^{\left\lfloor\frac{i}{j}\right\rfloor}\)
则答案为：\(Ans(B)\times Ans(A-1)^{-1}\)
现在考虑求解\(Ans(n)\)
变式，得到：
令\(A(n)=\prod_{i=1}^n\prod^i_{j=1}i^{\left\lfloor\frac{i}{j}\right\rfloor}\),\(B(n)=\prod_{i=1}^n\prod_{j=1}^nj^{\left\lfloor\frac{i}{j}\right\rfloor}\)
则\(Ans(n)=A(n)\times B(n)^{-1}\)
先考虑解决\(A\)
有：\(A(n)=\)
\[\prod_{i=1}^ni^{f(i)},f(i)=\sum_{j=1}^i\left\lfloor\frac{i}{j}\right\rfloor \]先来考虑求解\(f\)：
\[f(n)-f(n-1)=\sum_{i=1}^{n}\left(\left\lfloor\frac{n}{i}\right\rfloor-\left\lfloor\frac{n-1}{i}\right\rfloor\right) \]\(\left\lfloor\frac{n}{i}\right\rfloor-\left\lfloor\frac{n-1}{i}\right\rfloor=1\)，当且仅当\(i|n\)。
故：\(f(n)-f(n-1)=d(n)\)
\(d(n)\)可以欧拉筛\(O(n)\)求出。
故我们可以\(O(n)\)递推出\(f\)，进而递推求出整个\(A\)（\(A(n)=A(n-1)\times n^{f(n)}\)），复杂度\(O(n\log_2 n)\)，显然\(f(1)=1\)。
再有求\(B(n)\)
有：
\[\frac{B(n)}{B(n-1)}=\prod_{i=1}^ni^{\left\lfloor\frac{n}{i}\right\rfloor}=g(n) \]如果我们知道\(g\)，便可以快速递推\(B\)。考虑求解\(g\)。
直接看，貌似不咋能做，再来考虑设\(h(n)=\frac{g(n)}{g(n-1)}\)
则有：
\[h(n)=\prod_{i=1}^{n}i^{\left\lfloor\frac{n}{i}\right\rfloor-\left\lfloor\frac{n-1}{i}\right\rfloor} \]同样的，也只有\(i|n\)时，才有\(\left\lfloor\frac{n}{i}\right\rfloor-\left\lfloor\frac{n-1}{i}\right\rfloor=1\)。所以\(h(n)=\prod_{i|n}i\)。故\(h(n)\)也是积性函数，线性筛即可。
故\(B(n)=B(n-1)·g(n)\)，而\(g(n)\)可以通过\(h\)递推求出。
事实上，由于递推求\(A\)的过程是\(O(n\log n)\)的，故求解\(h,f\)的过程完全可以用倍数法，复杂度为\(O(\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor)\sim O(n\log n)\)。
最后对于一组询问\(Ans[l,r]=Ans(r)·Ans(l-1)=A(r)\times A(l-1)^{-1}\times B(r)^{-1}\times B(l-1)\)
最后真诚提示：十年OI一场空，不卡常数见祖宗。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 1000500
#define p 19260817
#define ll long long
#define re register
inline int read(){
register int x=0;register char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int h[N],g[N],A[N],B[N],Ans[N],f[N];
int n,m,t,d[N];
inline void init1(){//预处理出d,h，不影响复杂度的情况下，食用代码较简单的倍数法
for(re int i=1;i<=N-500;i++)h[i]=1;
for(re int i=1;i<=N-500;i++){
for(re int j=i;j<=N-500;j+=i){
h[j]=1ll*h[j]*i%p;
d[j]++;
}
}
}
inline void init2(){//预处理f,g
g[0]=1,f[0]=0;
for(re int i=1;i<=N-500;i++)f[i]=1ll*(f[i-1]+d[i])%p,g[i]=1ll*g[i-1]*h[i]%p;
}
inline int power(int a,int b){
re int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%p;
a=1ll*a*a%p;
b>>=1;
}
return ans;
}
inline void init3(){//预处理A,B,Ans
A[0]=B[0]=1;
for(re int i=1;i<=N-500;i++)A[i]=1ll*A[i-1]*power(i,f[i])%p,B[i]=1ll*B[i-1]*g[i]%p;
for(re int i=0;i<=N-500;i++)Ans[i]=1ll*A[i]*power(B[i],p-2)%p;
}
inline int get(int l,int r){
return 1ll*Ans[r]*power(Ans[l-1],p-2)%p;
}
void init(){
init1();
init2();
init3();
}
signed main(){
t=read();
init();
while(t--){
n=read(),m=read();
printf("%d\n",get(n,m));
}
return 0;
}