## Wednesday, July 22, 2015

### Codeforces 547C - Mike and Foam

Problem Statement:
547C - Mike and Foam

Solution:
The most important observation: since $$a_i <= 5 \times 10^5$$, the maximum number of distinct prime factors $$a_i$$ can have is 6, since $$2 \times 3 \times 5 \times 7 \times 11 \times 13 = 30030 < 5 \times 10^5$$ while $$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510 > 5 \times 10^5$$. This allows us to perform a fundamental counting principle called inclusion-exclusion principle.

First of all, suppose that on the shelf, we already have $$k$$ numbers, without losing generality, $$a_1, a_2, a_3, \ldots, a_k$$. We are going to place $$x$$ onto the shelf. We know that there are at most 6 prime factors of x, namely $$p_1,p_2, \ldots, p_6$$. We would like to find out how many more coprime pairs are introduced by the addition of $$x$$. Naturally, we want to check how many of $$(x, a_1), (x, a_2), (x, a_3), \ldots, (x, a_k)$$ are coprime.

If we do an O(n) linear check for each query $$x$$, then we will end up with an O(nq) solution which is undesirable. By making use of the fact that there are only 6 distinct prime factors $$x$$ can have, we can push down the O(n) term into a constant $$O(2^6)$$ using inclusion-exclusion principle.

Let $$d(n)$$ denotes the number of $$a_1, a_2, \ldots, a_k$$ on the shelf that is divisible by $$n$$. With this notation, we know that the number of new coprime pairs upon introduction of x onto the shelf is given by $$S = k - [ d(p_1) + d(p_2) + \ldots + d(p_6) ] + [ d(p_1p_2) + d(p_1p_3) + \ldots + d(p_5p_6) ] -$$$$[d(p_1p_2p_3) + d(p_1p_2p_4) + \ldots + d(p_4p_5p_6) ] + \ldots + d(p_1p_2p_3p_5p_6)$$.

Finally, we update d(n) by increasing each d(p) by 1, for all $$2^6$$ terms in S. For a query where x is already on the shelf, we do exactly the opposite of the above.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int n, q;
int a[200010];
int p[100], check[2000];
int d[500010];
int mark[200010];
vector<int> primes;
vector<vector<int> > factors;

int main(){
check[2] = 0;
for(int i=2;i*i<=500000;++i){
if(check[i])continue;
primes.push_back(i);
for(int j=2;i*j<=1000;++j){
check[i*j]=1;
}
}
scanf("%d%d",&n,&q);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
factors.push_back(vector<int>());
for(int j=0;j<primes.size();++j){
if(a[i]%primes[j]==0){
while(a[i]%primes[j]==0) a[i]/=primes[j];
factors[i].push_back(primes[j]);
}
}
if(a[i]!=1) factors[i].push_back(a[i]);
}
int x;
int cnt = 0;
long long prev = 0;
for(int qq=0;qq<q;++qq){
scanf("%d",&x);
--x;
int sz = factors[x].size();

if(mark[x]) {
int fact = 1;
for(int j=0;j<sz;++j){
fact *= factors[x][j];
}
}
d[fact]--;
}
--cnt;
}

int cur = cnt;
int fact = 1;
int mult = 1;
for(int j=0;j<sz;++j){
mult *= -1;
fact *= factors[x][j];
}
}
cur += mult*d[fact];
}
prev = prev + (mark[x] ? -cur : cur);
cout << prev << endl;

if(!mark[x]){
int fact = 1;
for(int j=0;j<sz;++j){
fact *= factors[x][j];
}
}
d[fact]++;
}
++cnt;
}

mark[x] ^=1;
}
return 0;
}