(codeforce547) c-mike and foam

Topic link ：Problem - 547C - Codeforces

subject ：

The sample input ： 

5 6
1 2 3 4 6
1
2
3
4
5
1

Sample output ：

0
1
3
5
6
2

The question ： A bar , Yes n Grow beer , from 1 To n. The first i A bottle of beer has ai Ml of foam .

Yes q A query . Each query is given a number , When the number is X Our beer is already on the shelf , Then take it off the shelf , Otherwise, you should put it on the shelf . After each inquiry , The score of the shelf should be output . The score of the shelf is to meet i<j And gcd(ai,aj)=1 The number of (i,j) The number of .

analysis ： If this problem is solved violently, the complexity is O(n*q), It must be impossible . For example, there are already m Grow beer and put it on the shelf , At this time, the score of the shelf is x, Then we put a bottle of beer on the shelf , Then the answer will be better than x One more increment delt, We just want to maintain this increment , So the score after putting in the beer is x+delt 了 . Empathy , If you take a bottle of beer from the shelf, the principle is the same .

Under what circumstances are two bottles of beer mutually qualitative ？ It must be that the two do not contain common qualitative factors , Look at the data range and find a The range of the array is 5e5, So because of 2*3*5*7*11*13*17=510510>5e5, So each number contains at most 6 A quality factor , Then we can Carry out the inclusion exclusion theorem for its prime factor , We use one num[s] Record the quality factor status as s The number of , Then we set A(p1,……,pk) Indicates that there is a qualitative factor p1,……,pk, Then because they are prime numbers , We can use product to maintain , Also is to use num[s] Record the quality factor status as s The number of . Because adding a number and deleting a number are basically similar , Next, I will add a number as an example to analyze the incremental calculation method ：

If the number of new additions is x, We are right. x We can get p1,p2,……,pk, Then our increment is , When the status is calculated s Don't forget to put the state after your contribution s The number of num[s] Add one .

The only difference between deleting a number and adding a number is , To delete a number, first change the status s The quantity of 1 Then calculate the contribution of this state , Adding a number is to calculate the contribution first and then the status s The number of add 1.

because a[] The size is less than 5e5 Of , So the prime factor of each number has at most 7 individual , So for each query, the complexity of the inclusion exclusion principle is at most C(7,0)+C(7,1)+C(7,2)+C(7,3)+C(7,4)+C(7,5)+C(7,6)+C(7,7)=2^7, So the complexity is definitely no problem .

Finally, I want to share a low-level problem I encountered when I was doing questions bug, But it's hard to find the mistake , Because for each inquiry is given the wine number t, So you can use it directly vis[t] Mark whether the wine is on the shelf , And I use it directly vis[a[t]] Indicates that the foam is a[t] Is your wine on the shelf , Since there may be two bottles of wine with different numbers, the foam is the same , So there's a problem .

Here is the code ：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e6+10;
int num[N];//num[st] Record the quality factor status of the wine on the current shelf as st The number of 
bool vis[N];
long long a[N],p[N];
long long ans;
long long add(long long x)
{
	// Preprocessing x The quality factor of  
	int tt=0;
	long long ans=0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			p[tt++]=i;
			while(x%i==0) x/=i;
		}
	}
	if(x!=1) p[tt++]=x;
	tt--;
	for(int s=0;s<1<<(tt+1);s++) 
	{
		long long f=1,t=1;
		for(int i=0;i<=tt;i++)
		{
			if(s>>i&1)
			{
				f*=-1;
				t*=p[i];
			}
		}
		if(t==1) t=0;//t==1 Description not updated , That is, the status is 0 
		ans+=f*num[t];
		num[t]++;
	}
	return ans;
}
long long sub(long long x)
{
	// Preprocessing x The quality factor of  
	int tt=0;
	long long ans=0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			p[tt++]=i;
			while(x%i==0) x/=i;
		}
	}
	if(x!=1) p[tt++]=x;
	tt--;
	for(int s=0;s<1<<(tt+1);s++) 
	{
		long long f=1,t=1;
		for(int i=0;i<=tt;i++)
		{
			if(s>>i&1)
			{
				f*=-1;
				t*=p[i];
			}
		}
		if(t==1) t=0;//t==1 Description not updated , That is, the status is 0
		num[t]--;
		ans+=f*num[t];
	}
	return ans;
}
int main()
{
	int n,q; 
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	while(q--)
	{
		long long t;
		scanf("%lld",&t);
		if(vis[t])
		{
			ans-=sub(a[t]);
			vis[t]=false;
		}
		else 
		{
			ans+=add(a[t]);
			vis[t]=true;
		}
		printf("%lld\n",ans);
	}
	return 0;
}