#C241108B. B
标签（Label）
- 离线操作
- 树状数组
网址（Website）
题目（Problem）
题解（Solution）
$\qquad$这是一个非常聪明地处理素数的方法。
$\qquad$首先求出 $1\sim 10^7$ 的素数，这个可以使用欧拉筛解决，然后对于每一个和数，记录这个数被哪个素数整除，在欧拉筛的时候也可以同时处理这个东西，并且欧拉筛的时候记录的被整除素数是连续的（这个在代码中有体现），相当于可以直接使用 while(x%prime[i]==0) x/=prime[i]; 语句，筛选出素数之后，后面就是标准的区间离线处理，发现 $n$ 是 $10^6$ ，考虑用树状数组或者线段树来处理，由于离线可以按右区间排序，所以从左到右处理的时候维护答案就好了。
出题者题解
算法分析
题目大意：给定一个序列 $A$ 查询区间内的数的所有质因子之积（每个质因子只算一次）。由于题目中 $n, T$ 同阶，下文中关于时间复杂度的分析将用 $n$ 代替 $T$，且 $M$ 表示值域。
20 分
我会暴力！
暴力分解每一个 $a_i$，每次询问暴力遍历 $l \sim r$。
时间复杂度 $O(n^2 + nM)$
50 分
这个范围中暴力分解每个数的质因子明显有些吃力。观察到值域比较小，那么可以用欧拉筛先筛出值域里面的所有素数，然后每次暴力按素数枚举，那么复杂度会降低到 $O(n \ln M)$，可能可以接受（出题人并没有尝试）；
或者我们在线筛的同时，标记好每一个合数的最小质因子（线筛的流程可以非常好的实现这一点）， 对于每个 $a_i$，每次不断除以他的最小质因子，那么复杂度就降成了 $O(n \log M)$。
做题经验告诉我们，要处理有关区间去重的问题时，我们常用到离线算法，那么可以想到莫队。
时间复杂度 $O(nw(M) n)$，可以通过 $50%$ 的数据。
特殊数据点 $1$
如果 $a_i$ 全部都是质数，容易发现题目退化为普通区间去重 。
有很多种乱搞做法均能通过本数据点，这里就不举例了。
特殊数据点 $2$
根据 $10^6$ 的数据范围那么很明显单次查询的复杂度应当是 $\log$ 的。
我们考虑能否用线段树来维护答案，假设要合并两个区间，这两个区间的答案分别是 $u, v$。
因为 $u$ 和 $v$ 中每个质因子只出现一次，那么 $u \times v$ 的话相同的质因子最多出现两次，而多的次数对答案的贡献正好是 $\gcd(u, v)$。
因为这个数据点不会爆 $\log \log long long$，因此只需使用线段树维护即可，每次合并答案时 $f_u = \gcd(f_{lson}, f_{rson}) \times f_{lson} \times f_{rson}$。
100 分
出题人做法
同样的还是考虑离线。对于 $a_i$ 的一个质因子 $p$，考虑 $p$ 对哪些答案会产生贡献。记 $i’$ 是在序列中上一个满足 $p$ 是 $a_{i’}$ 的质因子。那么 $p$ 就会对所有右端点在 $i$，左端点在 $[i’ + 1, i]$ 的所有区间的答案造成贡献。
接下来就很容易了，我们按照每次询问的右端点排序，用线段树维护对于当前的右端点的每个左端点的答案，而且线段树可以使用标记永久化优化，时间复杂度 $O(nw(M) \log n)$。
验题人做法
树状数组做法，和 $std1$ 做法差不多。
首先把每个数展开成为不同质因子的形式。展开之后，这是个长度为 $O(nw(n))$ 的数组 $a$。
维护一个数组，$last_i$ 表示在 $i$ 左边坐标最大的 $j$，且满足 $a_i = a_j$，若无则为 $0$。
这个数组很容易。
询问的区间也可以转化成为，查询区间 $[l, r]$ 之中，$last$ 值小于 $l$ 的所有数的乘积。
可以这么做：不断枚举 $l$，在 $l$ 增加的过程之中，在某个集合之中加入所有 $last$ 值小于 $l$ 的数字；然后，查询这个集合区间 $[l, r]$ 之中，所有数的乘积。
这一部分考虑维护一个前缀积，然后使用乘法逆元除掉应该减掉的部分，算就完事了。
时间复杂度：$O(nw(n) \log n)$。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 1012345;
const int S = 10123456;
bool ST;
bitset<S> isnp;
int pr[N],tot;
int kl[S];
void shai(){
isnp[1] = true;
For(i,2,S-5){
if(!isnp[i]) pr[++tot]=i;
for(int j=1;j<=tot&&i*pr[j]<=S-5;j++){
isnp[pr[j]*i]=true, kl[pr[j]*i]=pr[j];
if(i%pr[j]==0) break;
}
}
}
inline void mul(int &x,int y){x=1ll*x*y%mod;}
inline int inv(int x,int k=mod-2){
int res=1;while(k){
if(k&1) mul(res,x);
mul(x,x),k>>=1;
}return res;
}
struct BIT{
int c[S],n;inline void init(int s){n=s;fill(c,c+n+1,1);}
inline int lbt(int x){return x&-x;}
void update(int x,int v){for(int i=x;i<=n;i+=lbt(i))mul(c[i],v);}
int ask(int x){int res=1;for(int i=x;i;i-=lbt(i))mul(res,c[i]);return res;}
}B;
struct Wolf{int l,r,id;}q[N];
int f[N][16],cnt[N];
int n,m,a[N],as[N],pre[S];
void Solve(){
n=rd();For(i,1,n) a[i]=rd();
m=rd();For(i,1,m) q[i]={rd(),rd(),i};
For(i,1,n){
while(kl[a[i]]){
f[i][++cnt[i]] = kl[a[i]];
while(kl[a[i]]==f[i][cnt[i]]) a[i]/=kl[a[i]];
}
//如果剩下了一个质数，而且这个质数和前面的还不一样，就新加入一个
if(a[i] != f[i][cnt[i]]) f[i][++cnt[i]] = a[i];
}
sort(q+1,q+m+1,[&](auto a,auto b){return a.r<b.r;});
B.init(n);
for(int i=1,j=1;i<=n;i++){
For(s,1,cnt[i]){
if(pre[f[i][s]]) B.update(pre[f[i][s]],inv(f[i][s]));
B.update(i,f[i][s]), pre[f[i][s]]=i;
}
while(q[j].r==i) as[q[j].id]=1ll*inv(B.ask(q[j].l-1))*B.ask(q[j].r)%mod, j++;
}
For(i,1,m) printf("%d\n",as[i]);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
int T = 1;double Tim = clock();
shai();while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
