51Nod 1678 莫比乌斯反演

题目链接

---

题意： 给定$n$个数和$q$个询问，询问有两种： $1.$给定$i$和$val$，将$a[i]$的值更新为$val$ $2.$给定$i$，求${\sum }_{j=1}^{n}a[j](gcd(i,j)==1)$

---

思路：

考虑询问操作的实现： 由艾弗森约定，得： $$Ans=\sum _{j=1}^{n}a[j](gcd(i,j)==1)=\sum _{j=1}^{n}a[j]\sum _{d|gcd(i,j)}\mu [d]$$

转换枚举变量为$d$,则 $$Ans=\sum _{d=1}^n\mu [d]\ast \sum _{j=1}^{\lfloor \frac{n}{d}\rfloor }a[j\ast d]$$ ($d$为$i$的约数)

令 $$sum[x]=\sum _{i=1}^{\lfloor \frac{n}{x}\rfloor }a[i\ast x]$$

则： $$Ans=\sum _{d=1}^n\mu [d]\ast sum[d]$$ ($d$为$i$的约数)

故询问的复杂度为: $O(\sqrt{n})$

而对于更新操作，只需要更新$sum$中下标为$i$的约数的元素值，复杂度为：$O(\sqrt{n})$

另外需要预处理$sum$和$\mu$，复杂度为$O(n)$

总复杂度：$O(n+q\sqrt{n})$

---

代码：

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; typedef long long ll; #define lson rt<<1 #define rson rt<<1|1 const int A = 1e5 + 10; int a[A],sum[A],pri[A],mu[A],tot,n,q; bool vis[A]; void init(){ for(int i=0 ;i<=n ;i++) sum[i] = 0; for(int i=1 ;i<=n ;i++){ for(int j=i ;j<=n ;j+=i){ sum[i] += a[j]; } } tot = 0,mu[1] = 1; for(int i=2 ;i<A ;i++){ if(!vis[i]) pri[++tot] = i,mu[i] = -1; for(int j=1 ;j<=tot && i*pri[j] < A ;j++){ vis[i*pri[j]] = 1; if(i%pri[j] == 0){ mu[i*pri[j]] = 0; break; } mu[i*pri[j]] = -mu[i]; } } } void update(int x,int val){ for(int i=1 ;i*i<=x ;i++){ if(x%i == 0){ sum[i] = sum[i] - a[x] + val; if(i*i != x){ sum[x/i] = sum[x/i] - a[x] + val; } } } a[x] = val; } ll query(int x){ ll ans = 0; for(int i=1 ;i*i<=x ;i++){ if(x%i == 0){ ans += mu[i]*sum[i]; if(i*i != x){ ans += mu[x/i]*sum[x/i]; } } } return ans; } int main(){ scanf("%d%d",&n,&q); for(int i=1 ;i<=n ;i++) scanf("%d",&a[i]); init(); while(q--){ int type;scanf("%d",&type); if(type == 1){ int id,x; scanf("%d%d",&id,&x); update(id,x); } else{ int id; scanf("%d",&id); printf("%lld\n",query(id)); } } return 0; }