容斥+积性函数

容斥+积性函数

Mike and Foam

题意：

架子上有n瓶酒，初始架子为空，每次 *** 作询问一个编号的酒，如果不在架子上，那么就放到架子上，如果在架子上，那么就拿下来，每次询问回答一个分数。

分数的计算为：满足i

思路：

分析题意，满足gcd=1则表示两个数互质，即两个数没有公共的质因子，那么看到每个ai的范围为小于5e5，那么考虑质因数分解，每个数最多分解到6个质因子，比较少，并且发现对于每个质因子的次数是不需要的，那么对于每次的询问，我们可以更新一个增量即 *** 作编号x的酒，所引起对答案的增加或减少的量，对于这部分的计算，可以考虑采用容斥原理，即ax的质因子为,那么当添加x上去的时候，对答案的增量即为，架子上的酒的数量减去与x不互质的数的数量，那么就是：

那么就是减去含有pi的质因子的数的数量，然后加上含有pi*pj的质因子的数的数量，即可，然后进行二进制枚举，容斥即可。

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=5e5+5;
const int mod=1e9+7;
vector v[N];        //存储每个数的质因子
int a[N];                //保存每个因子的数的个数
ll num,ans;              //ans需要开ll，因为范围较大，并且要求的是对数
bool vis[N];             //标记每个编号的酒是否在架子上
void pre(int pos,int n){        //质因子的处理
	for(int i=2;i*i<=n;i++){
		int fg=0;
		while(n%i==0){
			n/=i;
			fg=1;
		}if(fg)v[pos].pb(i);
	}if(n>1)v[pos].pb(n);
	return ;
}
void query(int p,int op){
	ll tp=0;
	int n=v[p].size(); 
    for(int i=1;i<(1<>j)&1){
                cnt++;
                k*=v[p][j];           //计算出当前 *** 作对应的因子
            }
        }if(cnt&1)tp+=a[k];
        else tp-=a[k];
    }ans+=(num-tp)*op;               //num表示架子上的数量，tp表示将p拿下或者放上的贡献
    printf("%lldn",ans);
}
void update(int p,int op){
	int n=v[p].size();
    for(int i=0;i<(1<>j)&1)k*=v[p][j];
        }a[k]+=op;
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        pre(i,x);
    }
    while(m--){
    	int p;
       	cin>>p;
        if(!vis[p]){
            vis[p]=true;        //先询问，在更新
            query(p,1);
            update(p,1);
            num++;
        }else{                   //先更新，在询问
        	num--;
            vis[p]=false;
            update(p,-1);
            query(p,-1);
        }
    }return 0;
}