首页 > 代码库 > 51 Nod 1678 lyk与gcd
51 Nod 1678 lyk与gcd
1678 lyk与gcd
基准时间限制：2 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
这天，lyk又和gcd杠上了。
它拥有一个n个数的数列，它想实现两种操作。
1：将 ai 改为b。
2：给定一个数i，求所有 gcd(i,j)=1 时的 aj 的总和。
Input
第一行两个数n，Q(1<=n,Q<=100000)。接下来一行n个数表示ai(1<=ai<=10^4)。接下来Q行，每行先读入一个数A(1<=A<=2)。若A=1，表示第一种操作，紧接着两个数i和b。(1<=i<=n,1<=b<=10^4)。若B=2，表示第二种操作，紧接着一个数i。(1<=i<=n)。Output
对于每个询问输出一行表示答案。Input示例
5 31 2 3 4 52 41 3 12 4Output示例
97
1 #include<vector> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 #define N 100010 6 #define LL long long 7 vector<int>f[N],g[N]; 8 int a[N],n,ques; 9 bool q[N];10 long long sum[N];11 void Prepare(){12 int cnt=0;13 for(int i=2;i<=n;i++){14 if(!q[i])a[++cnt]=i;15 for(int j=1;j<=cnt;j++){16 if(a[j]*i>n) break;17 q[a[j]*i]=1;18 if(i % a[j] == 0) break;19 }20 }21 for(int i=1;i<=cnt;i++){22 for(int j=a[i];j<=n;j+=a[i]){23 int w=f[j].size();24 for(int k=0;k<w;k++){25 f[j].push_back(f[j][k]*a[i]);26 g[j].push_back(g[j][k]+1);27 }28 f[j].push_back(a[i]);29 g[j].push_back(1);30 }31 }32 }33 int main()34 {35 LL ans;36 scanf("%d%d",&n,&ques);37 Prepare();38 for(int i=1;i<=n;i++){39 scanf("%d",&a[i]);sum[1]+=a[i];40 for(int j=0;j<f[i].size();j++)41 sum[f[i][j]]+=a[i];42 }43 int x,pos,value;44 while(ques--){45 scanf("%d",&x);46 if(x==1){47 scanf("%d%d",&pos,&value);48 for(int i=0;i<f[pos].size();i++)49 sum[f[pos][i]]-=a[pos];50 sum[1]-=a[pos];a[pos]=value;sum[1]+=a[pos];51 for(int i=0;i<f[pos].size();i++)52 sum[f[pos][i]]+=a[pos];53 }54 else{55 ans=sum[1];56 scanf("%d",&pos);57 for(int i=0;i<f[pos].size();i++)58 if(g[pos][i] & 1)ans-=sum[f[pos][i]];59 else ans+=sum[f[pos][i]];60 61 printf("%lld\n",ans);62 }63 }64 return 0;65 }
比较基础的容斥题，我们预处理出每个i的所有素因子的组合，比如6={2,3,6}，那么我们对于a[6]将它加入到sum[2],sum[3],sum[6]中，统计答案时用容斥思想加加减减就行了。
51 Nod 1678 lyk与gcd
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。