https://acm.ecnu.edu.cn/contest/173/problem/E/
区间操作，线段树；
维护乘的次数和除的次数
最后答案是，div和mul共同作用的结果，
分两种来考虑，第一种是当前有足够多次1操作，所以当再来一次操作时，直接在此基础上进行修改，除就减，乘就加；
第二种比较复杂，当前没有足够多的1操作，（我们这里要足够多的1操作时为了让进行除操作时容易）当当前要进行除操作时，被update区间的minprime可能会发生变化，
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int M=1e5+5; 5 const int mod=1e9+7; 6 struct node{ 7 int mul,div; 8 }tree[M<<2]; 9 int a[M]; 10 ll quick_pow(ll a,ll b){ 11 ll t=1; 12 a%=mod; 13 while(b){ 14 if(b&1) 15 t=t*a,t%=mod; 16 b>>=1; 17 a=a*a%mod; 18 } 19 return t; 20 } 21 ll solve_div(ll x,int countt){ 22 if(x==1||countt==0) 23 return x; 24 ll m=sqrt(x+0.5); 25 for(ll i=2;i<=m;i++){ 26 while(x%i==0){ 27 x/=i; 28 countt--; 29 if(x==1||countt==0) 30 return x; 31 } 32 } 33 return 1; 34 } 35 int solve_mul(ll x,int countt){ 36 if(countt==0||x==1) 37 return x; 38 ll m=sqrt(x+0.5); 39 int y=x; 40 for(ll i=2;i<=m;i++) 41 if(x%i==0){ 42 y=i; 43 break; 44 } 45 x%=mod,y%=mod; 46 return x*quick_pow(y,countt)%mod; 47 } 48 void pushdown(int root,int l,int r){ 49 if(tree[root].div==0&&tree[root].mul==0) 50 return ; 51 int lc=root<<1,rc=root<<1|1; 52 int sign=min(tree[root].div,tree[lc].mul); 53 tree[lc].mul-=sign; 54 tree[lc].mul+=tree[root].mul; 55 tree[lc].div+=tree[root].div-sign; 56 57 sign=min(tree[root].div,tree[rc].mul); 58 tree[rc].mul-=sign; 59 tree[rc].mul+=tree[root].mul; 60 tree[rc].div+=tree[root].div-sign; 61 62 tree[root].div=tree[root].mul=0; 63 } 64 void update1(int L,int R,int root,int l,int r){ 65 if(L<=l&&r<=R){ 66 tree[root].mul++; 67 return ; 68 } 69 pushdown(root,l,r); 70 int midd=(l+r)>>1; 71 if(L<=midd) 72 update1(L,R,root<<1,l,midd); 73 if(R>midd) 74 update1(L,R,root<<1|1,midd+1,r); 75 } 76 void update2(int L,int R,int root,int l,int r){ 77 if(L<=l&&r<=R){ 78 if(tree[root].mul) 79 tree[root].mul--; 80 else 81 tree[root].div++; 82 return; 83 } 84 pushdown(root,l,r); 85 int midd=(l+r)>>1; 86 if(L<=midd) 87 update2(L,R,root<<1,l,midd); 88 if(R>midd) 89 update2(L,R,root<<1|1,midd+1,r); 90 } 91 void query(int &div,int &mul,int pos ,int root,int l,int r){ 92 if(l==r){ 93 int sign=min(mul,tree[root].div); 94 mul-=sign; 95 div+=tree[root].div-sign; 96 mul+=tree[root].mul; 97 return ; 98 } 99 int midd=(l+r)>>1; 100 if(pos<=midd) 101 query(div,mul,pos,root<<1,l,midd); 102 else 103 query(div,mul,pos,root<<1|1,midd+1,r); 104 int sign=min(mul,tree[root].div); 105 mul-=sign; 106 div+=tree[root].div-sign; 107 mul+=tree[root].mul; 108 } 109 int main(){ 110 int n,m; 111 scanf("%d%d",&n,&m); 112 for(int i=1;i<=n;i++) 113 scanf("%d",&a[i]); 114 /*for(int i=1;i<=n;i++){ 115 int flag=1; 116 for(int j=2;j*j<=a[i];i++){ 117 if(a[i]%j==0){ 118 minprime[i]=j; 119 flag=0; 120 break; 121 } 122 } 123 if(flag) 124 minprime[i]=i; 125 } 126 build(1,1,n);*/ 127 while(m--){ 128 int op; 129 scanf("%d",&op); 130 if(op==1){ 131 int x,y; 132 scanf("%d%d",&x,&y); 133 update1(x,y,1,1,n); 134 } 135 else if(op==2){ 136 int x,y; 137 scanf("%d%d",&x,&y); 138 update2(x,y,1,1,n); 139 } 140 else{ 141 int x; 142 scanf("%d",&x); 143 int LL=0,RR=0; 144 query(LL,RR,x,1,1,n); 145 // cout<<"!!"<<endl; 146 ll ans=0; 147 ans=solve_div(a[x],LL); 148 ans=solve_mul(ans,RR); 149 printf("%lld ",ans%mod); 150 } 151 } 152 return 0; 153 }