「题解」P5071 [Ynoi2015] 此时此刻的光辉
ZillionX
·
·
题解
下面约定 V 代表值域。
Description
给出一个长为 n 的序列 a，有 m 次询问，每次查询区间乘积约数个数的值，答案对 19260817 取模。
# Solution
显然由约数个数定理知，把区间内数做质因数分解后，$\prod (x_i+1)$ 即为答案（其中 $x_i$ 为质因数次数）。
考虑怎样朴素地做质因数分解，我们可以将 $\sqrt V$ 内质数线性筛出，然后 $\sqrt {a_i}$ 地枚举质数，判断是否 $a_i \bmod p_i=0$。若 $a_i$ 无法被分解，那么 $a_i$ 必定是个质数（这样 $>\sqrt V$ 的质数个数上界是 $\mathcal O(n)$），这样可以将预处理的复杂度做到 $\mathcal O(\sqrt V+n \dfrac{\sqrt {a_i}}{\log a_i})$。
查询的时候用莫队进行转移，不难做到查询 $\mathcal O((n+m) \sqrt n)$ 的复杂度（事实上，还有一个转移时质因数个数的复杂度，不过 $10^9$ 以内最多也就 $9$ 个质因数，影响不大；而且如果卡到了这个上界的话，那前面预处理的复杂度就会大大减小）。
将题目给出的 $n,m,V$ 的上界代入后，你会发现前面的复杂度基本是 $3 .5 \times 10^8$ 左右的，也就是说，只要我们实现足够精细，完全可以朴素地通过本题。
加上加速质因数分解的 Exact Division 和莫队奇偶性排序优化后，实现上述思路的代码[轻松](https://www.luogu.com.cn/record/list?pid=P5071&orderBy=1&status=&page=1)地跑进了 2021 年 8 月后的最优解第一页。配合 Pollard Rho 和根号分治，这份代码还可以应对 $V$ 更大的数据。
## 详细揭秘 Exact Division (by Min_25)
感谢 @AThousandMoon 等 UOJ 众神对我的指导。
对于任意 $a,b \in [0,2^k) \cap \mathbb N$，其中 $b >1$ 且 $b \bmod 2=1$，$a \bmod b=0$ 成立的充要条件是
$$ab^{-1} \bmod 2^k \le \left\lfloor\dfrac{2^k}{b}\right\rfloor$$
证明可以参见 [hly1204 对 Min_25 原作的中文译版](https://loj.ac/d/3068)~~，一般来说没有必要掌握，只需要记简单的结论就行了~~。
不妨取 $k=32$，那么通过 unsigned int 的自然溢出可以大大优化常数。
### 关于如何求 $\bmod 2^{32}$ 意义下 $b$ 的乘法逆元
可以通过牛顿迭代实现，也即 [P4512](https://www.luogu.com.cn/problem/P4512) 的做法：
$$G(x) \equiv 2 G_*(x) - F(x)G_*(x)^2 \pmod {x^n}$$
其中 $F(x)G_*(x) \equiv 1 \pmod {x^\frac{n}{2}}$，$F(x)G(x) \equiv 1 \pmod {x^n}$。
令 $x=2$ 就行了。
# Code
卡常留作读者练习。
```cpp
typedef unsigned int ui;
const int N=1e5+1,V=31623,P=3411,D=11,mod=19260817,M=3e6+1,K=V+N-1;
int n,m,tot,Ret=1,p[P],ds[N][D],dv[N][D],inv[M],b[N],u[K],Ans[N];
ui pv[P],pm[P];
bitset<V> vs;
unordered_map<int,int> mp;
inline char gc() {
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd() {
int x=0;
char ch=gc();
while (ch<'0' || ch>'9') ch=gc();
while (ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+(ch^48);
ch=gc();
}
return x;
}
inline void wr(int x) {
static int s[20];
int tot=0;
while (x) s[tot++]=x%10,x/=10;
while (tot) putchar(s[--tot]+48);
}
struct Qst {
int l,r,id;
bool operator<(const Qst &x) const {
return (b[l]^b[x.l])?l<x.l:((b[l]&1)?r<x.r:r>x.r);
}
}q[N];
inline ui inv32(ui n) {
ui x=1;
for (int i=0;i<5;i++) x*=2u-n*x;
return x;
}
void Init(int n) {
vs[1]=1;
tot=1,p[1]=2,vs[4]=1;
for (int i=3;i<=n;i++) {
if (vs[i]==0)
p[++tot]=i,pv[tot]=inv32(i),
pm[tot]=ui(-1)/i;
if (i*2<=n) vs[i*2]=1;
else continue;
if (!(i&1)) continue;
for (int j=2;j<=tot && i*p[j]<=n;j++) {
vs[i*p[j]]=1;
if (i*pv[j]<=pm[j]) break;
}
}
}
void Add(int x) {
for (int i=1;i<=ds[x][0];i++)
Ret=1ll*Ret*inv[u[dv[x][i]]+1]%mod,u[dv[x][i]]+=ds[x][i],
Ret=1ll*Ret*(u[dv[x][i]]+1)%mod;
}
void Del(int x) {
for (int i=1;i<=ds[x][0];i++)
Ret=1ll*Ret*inv[u[dv[x][i]]+1]%mod,u[dv[x][i]]-=ds[x][i],
Ret=1ll*Ret*(u[dv[x][i]]+1)%mod;
}
int main() {
Init(V-5);
n=rd(),m=rd();
int idt=tot;
ui x;
for (int i=1;i<=n;i++) {
x=rd();
int k=0;
if (!(x&1)) {
k++,ds[i][k]++,dv[i][k]=1,x>>=1;
while (!(x&1)) ds[i][k]++,x>>=1;
}
for (int j=2;j<=tot;j++)
if (x*pv[j]<=pm[j]) {
k++,ds[i][k]++,dv[i][k]=j,x*=pv[j];
while (x*pv[j]<=pm[j]) ds[i][k]++,x*=pv[j];
if (x==1) break;
}
if (x>1) {
k++,ds[i][k]++;
if (!mp[x]) mp[x]=++idt;
dv[i][k]=mp[x];
}
ds[i][0]=k;
}
inv[1]=1;
for (int i=2;i<M;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
int bk=sqrt(n);
for (int i=1;i<=n;i++) b[i]=(i-1)/bk+1;
for (int i=1;i<=m;i++)
q[i].l=rd(),q[i].r=rd(),q[i].id=i;
sort(q+1,q+m+1);
int L=1,R=0;
for (int i=1;i<=m;i++) {
while (L>q[i].l) Add(--L);
while (R<q[i].r) Add(++R);
while (L<q[i].l) Del(L++);
while (R>q[i].r) Del(R--);
Ans[q[i].id]=Ret;
}
for (int i=1;i<=m;i++) wr(Ans[i]),puts("");
return 0;
}
```