【数学】gcd
上個階段太頹也沒怎么寫題解導致直接炸掉，所以這個階段爭取繼續寫吧（咕咕咕）
題目內容
有 (n) 個正整數 (x_1) ~ (x_n)，初始時狀態均為未選。 有 (m) 個操作，每個操作給定一個編號 (i)，將 (x_i) 的選取狀態取反。 每次操作后，你需要求出選取的數中有多少個互質的無序數對。
數據范圍
(n,mleq 200000,x_ileq 500000)
思路
做數學題總是很需要磨。
首先解釋一波題意，選取狀態取反的是 (x_i)，互質的無序數對指的也是 (x) 間形成的數對。
首先考慮不修改怎么做，那么問題就是有 (n) 個正整數，求其中互質的數對的個數。
互質即 (gcd(a,b)=1)。那我們可以定義 (f[i]) 表示 (gcd=i) 的數對個數。考慮如何求出 (f[i])。定義 (g[i]) 表示 (gcd) 為 (i) 的倍數的數對個數。那么顯然有：
[g[i]=sumlimits_{ivert d}f[d]
]
嗯，這個顯然是莫比烏斯反演的第二個式子。那我們就可以得到 (f[i]) 的計算式了：
[f[i]=sumlimits_{ivert d}mu(fracze8trgl8bvbq{i})g[d]
]
那么現在的問題就是如何求出 (g[i])。定義 (s[i]) 表示 (i) 的倍數的個數。我們可以知道，(i) 的倍數組成的數對的 (gcd) 一定也是 (i) 的倍數。那么我們將其兩兩配對得到的方案數即是 (g[i])：
[g[i]=cfrac{s[i] imes(s[i]-1)}{2}
]
而 (s[i]) 很好求，當我們加入或刪除一個數的時候，直接枚舉其因數修改就可以了。記錄答案只需要刪掉原來的再加上現在的。那么帶修改的我們也完成了。
最后的答案就是 (f[1])，所以得到結論，(1) ~ (n) 中互質的數對的個數即是：
[sumlimits_{d=1}^nmu(d)g[d]
]
時間復雜度 (O(msqrt{max x}))，需要一點點卡常。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,m;
int a[maxn];
long long ans;
long long s[maxn],g[maxn];
bool vis[maxn];
inline int read(){
int x=0;bool fopt=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return fopt?x:-x;
}
int pri[maxn],mobius[maxn];
bool notpri[maxn];
inline void EulerSieve(){
notpri[0]=1;notpri[1]=1;mobius[1]=1;
for(int i=2;i<=5e5;i++){
if(!notpri[i]){
pri[++pri[0]]=i;
mobius[i]=-1;
}
for(int j=1;j<=pri[j]&&i*pri[j]<=5e5;j++){
notpri[i*pri[j]]=1;
if(i%pri[j]==0){
mobius[i*pri[j]]=0;
break;
}else mobius[i*pri[j]]=-mobius[i];
}
}
}
signed main(){
#ifndef LOCAL
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
#endif
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
EulerSieve();
for(register int i=1;i<=m;i++){
int x=read();vis[x]=!vis[x];
int d=vis[x]?1:-1;
for(register int j=1;j*j<=a[x];j++){
if(a[x]%j)continue;
s[j]+=d;
ans-=mobius[j]*g[j];
g[j]=s[j]*(s[j]-1)/2;
ans+=mobius[j]*g[j];
if(j*j!=a[x]){
s[a[x]/j]+=d;
ans-=mobius[a[x]/j]*g[a[x]/j];
g[a[x]/j]=s[a[x]/j]*(s[a[x]/j]-1)/2;
ans+=mobius[a[x]/j]*g[a[x]/j];
}
}
printf("%lld
",ans);
}
return 0;
}
總結
- 上一篇： earpods耳机正确戴法
- 下一篇： APP长期处于后台手机打开多个APP后进