51nod

分析

$$ \begin{aligned} &\sum_{i=1}^na_i[\gcd(i,x)=1]\\ =&\sum_{i=1}^na_i\sum_{d|i,d|x}\mu(d)\\ =&\sum_{d|x}\mu(d)\sum_{d|i}a_i \end{aligned} $$

于是只要对于每个 $d$ 暴力维护 $\sum_{d|i}a_i$ 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,a[N];

int p[N],v[N],mu[N],cnt=0;
inline void sieve(int n) {
    mu[1]=1;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,mu[i]=-1;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) mu[i*p[j]]=-mu[i];
            else { mu[i*p[j]]=0; break; }
        }
    }
}

ll s[N];
inline void modify(int p,int w) {
    for (re int i=1;i*i<=p;++i) {
        if (p%i) continue;
        s[i]+=w;
        if (i*i!=p) s[p/i]+=w;
    }
}
inline ll query(int p) {
    ll res=0;
    for (re int i=1;i*i<=p;++i) {
        if (p%i) continue;
        res+=mu[i]*s[i];
        if (i*i!=p) res+=mu[p/i]*s[p/i];
    }
    return res;
}

int main() { sieve(100000);
    n=read(),Q=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) modify(i,a[i]);
    while (Q--) {
        int op=read();
        if (op==1) {
            int i=read(),w=read();
            modify(i,w-a[i]),a[i]=w;
        } else {
            int i=read();
            printf("%lld\n",query(i));
        }
    }
    return 0;
}
最后修改:2020 年 03 月 14 日 05 : 55 PM