企业内部网站如何建设,怎么把网站的标题做的炫酷,asp网站文章自动更新,wordpress转换emlog昨天晚上用的镜像#xff0c;看的B的图片瞬间不想写了#xff08;而且这周作业还没碰#xff09;#xff0c;不过看到D题突然想做做#xff0c;于是有了下面的思路#xff0c;写了一个小时#xff0c;写完没交看了下榜单发现C题竟然过的人也不多#xff0c;看了看C题感…昨天晚上用的镜像看的B的图片瞬间不想写了而且这周作业还没碰不过看到D题突然想做做于是有了下面的思路写了一个小时写完没交看了下榜单发现C题竟然过的人也不多看了看C题感觉没啥思路就跑去补作业了~~ D. GCD of an Array
由于题目中要求gcd\gcdgcd取模显然gcd(x%mod,y%mod)≠gcd(x,y)%mod\gcd(x\%mod,y\%mod)\ne\gcd(x,y)\%modgcd(x%mod,y%mod)gcd(x,y)%mod于是很容易想到维护数组每个数质因数分解后的幂次xp1α1p2α2…pkαkxp_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}xp1α1p2α2…pkαk而pkp_kpk对最终gcd\gcdgcd的贡献是pkmin(α1,k,α2,k,…,αn,k)p_k^{\min(\alpha_{1,k},\alpha_{2,k},\dots,\alpha_{n,k})}pkmin(α1,k,α2,k,…,αn,k)
而对某个位置i×i×i×一个数xp1αi,1p2αi,2…pkαi,kxp_1^{\alpha_{i,1}}p_2^{\alpha_{i,2}}\dots p_{k}^{\alpha_{i,k}}xp1αi,1p2αi,2…pkαi,k则表示修改αi,1,αi,2,…,αi,k\alpha_{i,1},\alpha_{i,2},\dots,\alpha_{i,k}αi,1,αi,2,…,αi,k这些值准确来说是上一个数我们只需要记录之前的值把之前的贡献减去然后把现在的贡献加上即可
而对于贡献的维护我们需要一个能够支持插入删除最小值的数据结构这里使用multiset\text{multiset}multiset trick对于初始数组可以看出一个操作i,aii,a_ii,ai
时间复杂度O{(nm)max(ai)logn}O\{(nm)\sqrt{\max(a_i)}\log{n}\}O{(nm)max(ai)logn}
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#pragma GCC optimize(2)
#includeset
#includemap
#includeiostream
#includealgorithm
using namespace std;
using lllong long;
constexpr ll mod1e97;
constexpr int N200010;
int a[N],n,m;
ll d;
multisetint s[N];
mapint,int mp[N];
ll qmi(ll a,ll b)
{ll res1;while(b){if(b1) resres*a%mod;b1;aa*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) dd*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) dd*qmi(i,*s[i].begin())%mod;}else{mp[k][i]cnt;s[i].insert(mp[k][i]);if(s[i].size()n) dd*qmi(i,*s[i].begin())%mod;}
}
void divide(int k,int x)
{for(int i2;ix/i;i)if(x%i0){int cnt0;while(x%i0) x/i,cnt;insert(k,i,cnt);}if(x1) insert(k,x,1);
}
int main()
{IO;cinnm;for(int i1;in;i) cina[i];d1;for(int i1;in;i) divide(i,a[i]);while(m--){int i,x;cinix;divide(i,x);coutd\n;}return 0;
}
