題意：小花梨得到了一個長度為?的數組?，現在要對它進行三種操作：

? ? ? ? ? ? 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; } View Code

?

轉載于:https://www.cnblogs.com/Willems/p/10889132.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的小花梨的数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。