昨天晚上用的鏡像，看的B的圖片瞬間不想寫了（而且這周作業還沒碰），不過看到D題突然想做做，于是有了下面的思路，寫了一個小時，寫完沒交看了下榜單發現C題竟然過的人也不多，看了看C題感覺沒啥思路就跑去補作業了~~

---

D. GCD of an Array

由于題目中要求$\gcd$取模，顯然$\gcd (x\%mod,y\%mod)=\gcd (x,y)\%mod$，于是很容易想到維護數組每個數質因數分解后的冪次$x=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}$，而$p_k$對最終$\gcd$的貢獻是$p_k^{\min ({\alpha }_{1,k},{\alpha }_{2,k},\dots ,{\alpha }_{n,k})}$

而對某個位置$i\times$一個數$x=p_1^{{\alpha }_{i,1}}{p}_2^{{\alpha }_{i,2}}\dots p_k^{{\alpha }_{i,k}}$則表示修改${\alpha }_{i,1},{\alpha }_{i,2},\dots ,{\alpha }_{i,k}$這些值（準確來說是＋上一個數，我們只需要記錄之前的值，把之前的貢獻減去，然后把現在的貢獻加上即可）

而對于貢獻的維護我們需要一個能夠支持插入，刪除，最小值的數據結構，這里使用$\text{multiset}$
trick：對于初始數組可以看出一個操作$i,a_i$

時間復雜度：$O\{(n+m)\sqrt{\max (a_i)}\log n\}$

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr) #pragma GCC optimize(2) #include<set> #include<map> #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr ll mod=1e9+7; constexpr int N=200010; int a[N],n,m; ll d; multiset<int> s[N]; map<int,int> mp[N]; ll qmi(ll a,ll b) {ll res=1;while(b){if(b&1) res=res*a%mod;b>>=1;a=a*a%mod;}return res; } ll inv(ll x) {return qmi(x,mod-2); } void insert(int k,int i,int cnt) {if(mp[k].count(i)){if(s[i].size()==n) d=d*inv(qmi(i,*s[i].begin()))%mod;s[i].erase(s[i].find(mp[k][i]));mp[k][i]=mp[k][i]+cnt;s[i].insert(mp[k][i]);if(s[i].size()==n) d=d*qmi(i,*s[i].begin())%mod;}else{mp[k][i]=cnt;s[i].insert(mp[k][i]);if(s[i].size()==n) d=d*qmi(i,*s[i].begin())%mod;} } void divide(int k,int x) {for(int i=2;i<=x/i;i++)if(x%i==0){int cnt=0;while(x%i==0) x/=i,cnt++;insert(k,i,cnt);}if(x>1) insert(k,x,1); } int main() {IO;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];d=1;for(int i=1;i<=n;i++) divide(i,a[i]);while(m--){int i,x;cin>>i>>x;divide(i,x);cout<<d<<'\n';}return 0; }

總結

以上是生活随笔為你收集整理的codeforces1493 D. GCD of an Array（数论）的全部內容，希望文章能夠幫你解決所遇到的問題。

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