Codeforces Round #705 (Div. 2) D. GCD of an Array
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Round #705 (Div. 2) D. GCD of an Array,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2346字,纯文字阅读大概需要4分钟。
内容图文
题目大意
你会得到一个数组a,并且会有q个查询,给定两个数字i和x,将a[i]乘以x,输出每次查询后的数组a的gcd
题解
牛客的寒假训练营有一道比这个简单的同类型题,这里上个牛客的传送门,我们先考虑如果数组a没有被修改,应该怎么求他们的gcd,很显然,我们可以将每个数字进行质因子分解,这样数组a中所有数都有的质因子,一定就是他们的gcd的质因子。再考虑如果有修改会怎么样,如果a[i]乘x,将x也质因子分解,如果分解出的质因子,别的数字也有,并且别的数字的此质因子数量均大于a[i]*x的此质因子数量,那么gcd的此质因子也可以多一个,换句话说,gcd可以扩大此质因子倍。由此我们得出解法,用multiset存每一个数的对应质因子的数量,然后判断是否其中每个质因子的最小值是否扩大就好了,上代码
#include<cstdio>
#include<cstdio>
#include<map>
#include<set>
#define MAX 1005
#define MAXN 200005
using namespace std;
const long long MOD=1e9+7;
int findprim[MAX];
int prim[MAX];
int primnum;
map<int,int> all_prim[MAXN];
multiset<int>cnt[MAXN];
long long ans=1;
void init(){
findprim[0]=findprim[1]=1;
for(int i=2;i<=MAX;i++){
if(!findprim[i]){
for(int j=i+i;j<=MAX;j+=i){
findprim[j]=1;
}
}
}
for(int i=2;i<=MAX;i++){
if(!findprim[i]){
prim[primnum++]=i;
}
}
return ;
}
void tryans(int prim,int n,int size){
if(cnt[prim].size()<n){
return ;
}
for(int i=0;i<size;i++){
ans*=prim;
ans%=MOD;
}
return ;
}
int main(){
init();
int n,q,a,m;
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++){
scanf("%d",&a);
for(int j=0;prim[j]*prim[j]<=a&&j<primnum;j++){
int flag=0;
while(!(a%prim[j])){
all_prim[i][prim[j]]++;
a/=prim[j];
flag=1;
}
if(flag){
cnt[prim[j]].insert(all_prim[i][prim[j]]);
tryans(prim[j],n,*cnt[prim[j]].begin());
}
}
if(a!=1){
all_prim[i][a]++;
cnt[a].insert(1);
tryans(a,n,*cnt[a].begin());
}
}
for(int i=0;i<q;i++){
scanf("%d%d",&m,&a);
m--;
for(int j=0;prim[j]*prim[j]<=a&&j<primnum;j++){
int flag=0,flag2=0,thisnum=0;
while(!(a%prim[j])){
all_prim[m][prim[j]]++;
if(all_prim[m][prim[j]]==1){
flag2=1;
}
a/=prim[j];
flag=1;
thisnum++;
}
if(flag){
int min;
if(flag2){
min=0;
}else{
min=*cnt[prim[j]].begin();
cnt[prim[j]].erase(cnt[prim[j]].find(all_prim[m][prim[j]]-thisnum));
}
cnt[prim[j]].insert(all_prim[m][prim[j]]);
tryans(prim[j],n,*cnt[prim[j]].begin()-min);
}
}
if(a!=1){
int min;
all_prim[m][a]++;
if(all_prim[m][a]==1){
min=0;
}else{
min=*cnt[a].begin();
cnt[a].erase(cnt[a].find(all_prim[m][a]-1));
}
cnt[a].insert(all_prim[m][a]);
tryans(a,n,*cnt[a].begin()-min);
}
printf("%lld\n",ans);
}
return 0;
}
有一说一,感觉D比C简单呀Q^Q,如果解释的有误,欢迎指正
内容总结
以上是互联网集市为您收集整理的Codeforces Round #705 (Div. 2) D. GCD of an Array全部内容,希望文章能够帮你解决Codeforces Round #705 (Div. 2) D. GCD of an Array所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。