/*51 nod 1439 互质对(Moblus容斥)problem:有n个数字，a[1],a[2],…,a[n]。有一个集合，刚开始集合为空。然后有一种操作每次向集合中加入一个数字或者删除一个数字。每次操作给出一个下标x，如果a[x]已经在集合中，那么就删除a[x],否则就加入a[x]。问每次操作之后集合中互质的数字有多少对。注意，集合中可以有重复的数字，两个数字不同当且仅当他们的下标不同。比如a[1]=a[2]=1。那么经过两次操作1，2之后，集合之后存在两个1，里面有一对互质。solve:问题可以看成每次添加后,增加or减少的这个数与集合中数互质的个数.于是就成了求一个数与一个集合中互质数的个数. 用数组来记录集合中数的约数情况然后再利用容斥原理(Moblus实现的). 就能求出GCD为1的个数hhh-2016/10/01-22:28:16*/#pragma comment(linker,"/STACK:124000000,124000000")#include <algorithm>#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <vector>#include <map>#include <queue>#include <functional>#include <math.h>#define lson  i<<1#define rson  i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define key_val ch[ch[root][1]][0]using namespace std;const int maxn = 5e5 + 1000;const int inf = 0x3f3f3f3f;const ll mod = 1000000007;const double eps = 1e-7;template<class T> void read(T&num){    char CH;    bool F=false;    for(CH=getchar(); CH<‘0‘||CH>‘9‘; F= CH==‘-‘,CH=getchar());    for(num=0; CH>=‘0‘&&CH<=‘9‘; num=num*10+CH-‘0‘,CH=getchar());    F && (num=-num);}int stk[70], tp;template<class T> inline void print(T p){    if(!p)    {        puts("0");        return;    }    while(p) stk[++ tp] = p%10, p/=10;    while(tp) putchar(stk[tp--] + ‘0‘);    putchar(‘\n‘);}int tot;int is_prime[maxn];ll mu[maxn];int prime[maxn];void Moblus(){    tot = 0;    mu[1] = 1;    memset(is_prime,0,sizeof(is_prime));    for(int i = 2; i < maxn-10; i++)    {        if(!is_prime[i])        {            prime[tot++] = i;            mu[i] = -1;        }        for(int j = 0; j < tot && i*prime[j] < maxn-10; j++)        {            is_prime[i*prime[j]] = 1;            if(i % prime[j])            {                mu[i*prime[j]] = -mu[i];            }            else            {                mu[i*prime[j]] = 0;                break;            }        }    }}int vis[maxn];int hav[maxn];int a[maxn];int main(){    Moblus();    int num = 0;    int n,m;    read(n),read(m);    for(int i =1 ;i <= n;i++)        read(a[i]);    ll ans = 0;    int x;    for(int i =1 ;i <= m;i++)    {        ll tans = 0;        read(x);        int t = 1;        if(vis[x])            t = -1;        for(int j = 1;j * j <= a[x];j ++)        {            if(a[x]%j)                continue;            tans += (ll)mu[j] * hav[j];            hav[j] += t;            if(j * j != a[x]){                tans += (ll)mu[a[x]/j] * hav[a[x]/j];                hav[a[x]/j] += t;            }        }        vis[x]+=t;        num += t;        ans += (ll)tans*t;        if(a[x] == 1 && vis[x] == 0)            ans += 1LL;        printf("%I64d\n",ans);    }    return 0;}