题意：小花梨得到了一个长度为??的数组??，现在要对它进行三种操作：
? 1 ?? ?? 对所有的?? ∈ [??, ??], ??[??] = ??[??] ∗ ????????????????(??[??])
? 2 ?? ?? 对所有的?? ∈ [??, ??], ??[??] = ??[??] / ????????????????(??[??])
? 3 ?? 求??[??]的值 ????????????????(??) = { 1 (?? = 1) ??的最小素因子(?? ≥ 2) 现在给出初始数组??，对其进行??次操作，对于第三种操作输出结果。
题目链接：https://acm.ecnu.edu.cn/contest/173/problem/E/
思路：
每个数字x可以表示成pq11∗pq22∗...∗pqnn，多次操作之后，一定是将前面的一些素因子除去，在乘以当前的素因子的x次方即可
线段树维护两个tag，乘法标记和除法标记
乘法标记直接加即可
如果存在乘法标记，那么除法标记就抵消乘法标记，否则添加新的除法标记
（都是从题解 copy过来的。。。） （题解：http://fzl123.top/archives/998）
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define rep(i,j,k) for(int i=j;i<=k;i++) #define dep(i,j,k) for(int i=k;i>=j;i--) #define INF 0x3f3f3f3f #define mem(i,j) memset(i,0,sizeof(i)) #define make(i,j) make_pair(i,j) #define pb push_back #define lc(r) r<<1 #define rc(r) r<<1|1 using namespace std; const int N=1e5+5; const int mod=1e9+7; int M[N<<2];///乘的次数 int D[N<<2];///除的次数 bool vis[N]; int pre[1001],tot; vector<int>G[N];///存质因子 void init() { ///预处理1000内的质数 for(int i=2;i<=1000;i++) { if(!vis[i]) pre[++tot]=i; rep(j,1,tot) { if(i*pre[j]>1000) break; vis[i*pre[j]]=1; if(i%pre[j]==0) break; } } } void pushdown(int root,int l,int r) { if(D[root] || M[root]) { if(M[lc(root)]>=D[root]) M[lc(root)]-=D[root]; ///乘和除 是 可以相互抵消的 else D[lc(root)]+=(D[root]-M[lc(root)]),M[lc(root)]=0; if(M[rc(root)]>=D[root]) M[rc(root)]-=D[root]; else D[rc(root)]+=(D[root]-M[rc(root)]),M[rc(root)]=0; M[lc(root)]+=M[root]; M[rc(root)]+=M[root]; M[root]=D[root]=0; } } void updat(int root,int l,int r,int x,int y,int op) { ///跟新 if(x<=l && r<=y) { if(op==1) M[root]++; else { if(M[root]) M[root]--; else D[root]++; } return ; } pushdown(root,l,r); int m=(l+r)>>1; if(x<=m) updat(lc(root),l,m,x,y,op); if(y>m) updat(rc(root),m+1,r,x,y,op); } void query(int root,int l,int r,int x,int &Mn,int &Dn) { ///查询 if(l==r) { Dn=D[root]; Mn=M[root]; return ; } pushdown(root,l,r); int m=(l+r)>>1; if(x<=m) query(lc(root),l,m,x,Mn,Dn); else query(rc(root),m+1,r,x,Mn,Dn); } LL ksm(LL a,LL b,LL mod) {///快速幂 LL ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int main() { int n,m,a; init(); scanf("%d %d",&n,&m); rep(i,1,n) { scanf("%d",&a); rep(j,1,tot) { ///分解质因子 if(pre[j]*pre[j]>a) break; while(a%pre[j]==0) a/=pre[j],G[i].pb(pre[j]); } if(a>1) G[i].pb(a); } int ch,x,y; rep(i,1,m) { scanf("%d",&ch); if(ch==1) { scanf("%d %d",&x,&y); updat(1,1,n,x,y,1); } else if(ch==2) { scanf("%d %d",&x,&y); updat(1,1,n,x,y,2); } else { scanf("%d",&x); int counm=0,cound=0; query(1,1,n,x,counm,cound); ///先除再乘，因为除完后，最小素因子可能会变 if(cound>=G[x].size()) { puts("1"); continue; } ///除的次数，比能分解出来的因子都多，那就是1了 int ans=1; int tmp=G[x][cound]; rep(j,cound,G[x].size()-1) ans*=G[x][j]; ///除完后剩下的因子的乘积 ans=(LL)ans*ksm(tmp,counm,mod)%mod; ///乘上 最小素因子的 counm次方 就是答案了 printf("%d\n",ans); } } return 0; }
原文：https://www.cnblogs.com/Willems/p/10889132.html
