【51Nod1439】互質對

有n個數字，a[1],a[2],…,a[n]。有一個集合，剛開始集合為空。然後有一種操作每次向集合中加入一個數字或者删除一個數字。每次操作給出一個下标x(1 ≤ x ≤ n)，如果a[x]已經在集合中，那麼就删除a[x],否則就加入a[x]。

問每次操作之後集合中互質的數字有多少對。

注意，集合中可以有重複的數字，兩個數字不同當且僅當他們的下标不同。

比如a[1]=a[2]=1。那麼經過兩次操作1，2之後，集合之後存在兩個1，裡面有一對互質。

Input

單組測試資料。

第一行包含兩個整數n 和 q (1 ≤ n, q ≤ 2 × 10^5)。表示數字的種類和查詢數目。

第二行有n個以空格分開的整數a[1],a[2],…,a[n] (1 ≤ a[i] ≤ 5 × 10^5),分别表示n個數字。

接下來q行，每行一個整數x(1 ≤ x ≤ n)，表示每次操作的下标。

Output

對于每一個查詢，輸出目前集合中互質的數字有多少對。

Input示例

樣例輸入1

5 6

1 2 3 4 6

1

2

3

4

5

1

樣例輸入2

2 3

1 1

1

2

1

Output示例

樣例輸出1

1

3

5

6

2

樣例輸出2

1

題解

容易知道ans加減就是求這個數與集合中元素互質的個數，計算每個數的因子，如6，有因子1，2，3，6，計算含有1，2，3，6因子的數的個數，容斥原理計算與6互質的數。

注意1與1互質，1不與1本身互質。

代碼

#include<bits/stdc++.h>
#define mod 1000000007
#define inf 1000000005
#define pa pair<int,int>
typedef long long ll;
using namespace std;
inline int read()
{
    int x=,f=;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')f=-;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n,tot,q,a[],c[];
bool flag[],in[];
int p[],mu[];
void Moblus()
{
    mu[]=;
    for (int i=;i<=;i++)
    {
        if (!flag[i]) p[++tot]=i,flag[i]=,mu[i]=-;
        for (int j=;j<=tot&&i*p[j]<=;j++)
        {
            flag[i*p[j]]=;mu[i*p[j]]=-mu[i];
            if (i%p[j]==){mu[i*p[j]]=;break;}
        }
    }
}
int main()
{
    Moblus();
    n=read();q=read();
    for (int i=;i<=n;i++) a[i]=read();
    while (q--)
    {
        int x=read(),sum=;
        for (int i=;i*i<=a[x];i++)
        {
            if (a[x]%i) continue;
            sum+=(ll)mu[i]*c[i];
            c[i]+=in[x]?-:;
            if (i*i!=a[x])
            {
                sum+=(ll)mu[a[x]/i]*c[a[x]/i];
                c[a[x]/i]+=in[x]?-:;
            }
        }
        if (in[x]) ans-=sum-(a[x]==?:);else ans+=sum;
        in[x]^=;
        printf("%lld\n",ans);
    }
    return ;
}