基准时间限制：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 3
1 2 3 4 5
2 4
1 3 1
2 4
Output示例
9
7
看了讨论区才会做。。。
#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1000051;
int prime[MAX_N];//素数表
bool is_prime[MAX_N+1];
//返回n以内的素数的个数
int sieve(int n)
{
int p=0;
for(int i=0;i<=n;i++)is_prime[i]=true;
is_prime[0]=is_prime[1]=false;
for(int i=2;i<=n;i++)
{
if(is_prime[i])
{
prime[p++]=i;//素数打表
for(int j=2*i;j<=n;j+=i)is_prime[j]=false;//去掉已有素数的倍数
}
}
return p;
}
int n,q;
int a[100005];
int A;
int sum=0;
int primecnt;
int val[100005];//val [x] = y 表示对于含有x因子的下标的数值总和为y
vector<int>v;
void update(int x,int y)//更新
{
sum-=a[x];
for(int i=1;i*i<=x;i++)
{
if(x%i==0)
{
if(i*i!=x)
val[x/i]+=y-a[x];
val[i]+=y-a[x];
}
}
a[x]=y;
sum+=a[x];
}
void getprime(int n)//素因子分解
{
v.clear();
int temp,i,now;
temp=(int)((double)sqrt(n)+1);
now=n;
for(i=2;i<=temp;++i)if(now%i==0){
v.push_back(i);
while(now%i==0){
now/=i;
}
}
if(now!=1){
v.push_back(now);
}
}
int query(int x)
{
getprime(x);
int res=0,len=v.size();
for(int i=1;i<(1<<len);i++)//枚举所有非空子集
{
int cnt=0,t=1;
for(int j=0;j<len;j++)
{
if(i&(1<<j))
{
t*=v[j];
cnt++;
}
}
//容斥原理计数,若集合大小为奇数，则加上，否则减掉
if(cnt&1)
res+=val[t];
else
res-=val[t];
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
primecnt=sieve(1000050);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);sum+=a[i];
}
//初始化val数组
for(int i=1;i<=n;i++)
for(int j=1;i*j<=n;j++)
val[i]+=a[i*j];
int i,b;int ans=0;
while(q--)
{
scanf("%d",&A);
if(A==1)
{
scanf("%d%d",&i,&b);
update(i,b);
}
else
{
scanf("%d",&i);
ans=query(i);
printf("%d\n",sum-ans);
}
}
}