[CF 547C] Mike and Foam

作法：

首先可以把問題化為：支援一個資料結構，可以加入和刪除數，並且詢問目前裡面有幾個數和給定的某個數互質。設當前詢問的數是$x$，其因數由為$d_1,...,d_r$，那麼$x$和所有當前裡面的數的 gcd 值只有可能是$x$的因數，因此設目前總共有$a_i$的數和$x$的 gcd 等於$i$，則只有$x$的因數的$a$值非$0$，而我們想求的就是$a_1$。單一個$a_i$的值不容易求，但如果令$num_i$代表目前這些數裡面有幾個數是$i$的倍數，顯然可以在加入和刪除一個數時維護好$num_i$的陣列，那麼考慮$num_{d_i}$，他其實就會等於所有滿足$d_i | d_j$ 的$a_{d_j}$ 的總和，也就是如果令$A_i=\{ d_j | d_j\%d _i=0 \}$，那麼$\displaystyle num_{d_i}=\sum_{t\in A_i}a_t$，因此現在要用已知的$num_{d_i}$們的式子來求出$a_1$。再來就有點類似莫比烏斯反演的概念了，那東西的詳細可以參考維基，其實和這題一樣本質上來說就是排容原理。不妨設$d_1,...,d_k$就是$x$的所有質因數（不包含$1$），那麼考慮集合$A_1,...,A_k$，跟他們的宇集$\{ d_1,...,d_r \}$，並且以下記$|S|$代表$S$中所有元素的$a$值的和。可以得到$A_1\bigcup A_2\bigcup ... \bigcup A_k$包含了所有$x$的非$1$的因數，因此用宇集扣掉他之後就只剩下$1$，也就是我們要求扣掉之後的集合內元素的權值和（雖然他只有一個元素）。這時就可以用排容了，首先宇集的權值和就是$num_1$，再來要扣掉$|A_1|,...,|A_k|$，由上面的結論可以知道$|A_i|$就是$num_{d_i}$，直接代入即可。再來要加回長的像$|A_i\bigcap A_j|$的這種東西，這裡就是莫比烏斯變換關鍵的地方，因為$d_i$和$d_j$是兩個$x$的不同的質因數，所以他們互質，而回到$A_i$的定義，他裡面蒐集了所有是$d_i$倍數的$x$的因數，所以由$d_i,d_j$互質就可以得到$|A_i\bigcap A_j|=num_{i\cdot j}$，因為他們的交集就代表著滿足他是$d_i,d_j$倍數的$x$的因數，所以是滿足他是$d_i\cdot d_j$倍數的$x$的因數，所以就可以化簡成$num_{i\cdot j}$了。到了好幾個$A$交集在一起時一樣可以融合起來變成一個$num$值，於是這樣就成功求出答案了。

而實作的方法又轉了個彎，因為注意到上面那條式子裡面，我們會用到的$num$值的下標都是「沒有平方因子的數」(square-free)，或是說把他質因數分解的話會分成好幾個不同的質數的一次方相乘，而$num$值前面的係數則和當前下標的質因數個數有關，若個數為奇數則為$-1$，若為偶數則為$1$，這東西就是莫比烏斯函數，因此在計算上我們只要先把$x$的所有因數找出來，求出所有因數的$num$值乘上其莫比烏斯函數的值的總和就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=500000+10 ;
 
int mu[maxn],di[maxn] ;
bool vis[maxn] ;
void getmu()
{
    for(int i=2;i*i<maxn;i++) if(!vis[i])
        for(int j=i*i;j<maxn;j+=i) vis[j]=1 , di[j]=i ;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i]){mu[i]=-1 ; continue ;}
        mu[i]= (i/di[i])%di[i] ? mu[i/di[i]]*-1 : 0 ;
    }
}
 
int a[maxn],num[maxn] ;
bool on[maxn] ;
vector<int> vd ;
void getdiv(int x)
{
    vd.clear() ;
    for(int i=1;i*i<=x;i++) if(x%i==0)
    {
        vd.push_back(i) ;
        if(i*i!=x) vd.push_back(x/i) ;
    }
}
 
int getval()
{
    int ret=num[1] ;
    for(auto i : vd) ret+=num[i]*mu[i] ;
    return ret ;
}
 
inline void add(int x)
{
    for(auto i : vd) num[i]+=x ;
}
 
main()
{
    getmu() ;
    int n,Q ; scanf("%d%d",&n,&Q) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    LL ans=0 ;
    while(Q--)
    {
        int x ; scanf("%d",&x) ;
        getdiv(a[x]) ;
        if(!on[x]) ans+=getval() , add(1) , on[x]=1 ;
        else add(-1) , ans-=getval() , on[x]=0 ;
        printf("%I64d\n",ans) ;
    }
}