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]) {
            for(int mask = 1; mask < (1<<sz);++mask){
                int fact = 1;
                for(int j=0;j<sz;++j){
                    if(mask&(1<<j)){
                        fact *= factors[x][j];
                    }
                }
                d[fact]--;
            }           
            --cnt;
        }

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

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

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