# CFR 547 C. Mike and Foam ( Mobius Inversion )

Problem - 547C - Codeforces

N, Q ≤ 2e5
max{ A } ≤ 5e5
TL: 2000 ms

O( MAXA lg MAXA + Q * 2^6 ) / O( MAXA )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 2e5;
const int MAXA = ( int ) 5e5;

int N, Q;
int A[ MAXN ];
int mu[ MAXA + 1 ];
int in_shelf[ MAXN ];
int np[ MAXA + 1 ];
vector< int > pf[ MAXA + 1 ];
int bai_cnt[ MAXA + 1 ];

signed main(){
{ // preprocess mu
mu[ 1 ] = 1;
for( int i = 1; i < MAXA; ++i ){
for( int j = i + i; j <= MAXA; j += i ){
mu[ j ] -= mu[ i ];
}
}
}
{ // preprocess prime factors
for( int i = 2; i < MAXA; ++i ){
if( np[ i ] ) continue;
pf[ i ].emplace_back( i );
for( int j = i + i; j <= MAXA; j += i ){
np[ j ] = 1;
pf[ j ].emplace_back( i );
}
}
}
ios::sync_with_stdio( 0 );
cin >> N >> Q;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
long long ans = 0;
for( int qi = 0; qi < Q; ++qi ){
int idx; cin >> idx; --idx;
int sign = in_shelf[ idx ] ? -1 : 1;
ans -= 1LL * mu[ 1 ] * bai_cnt[ 1 ] * ( bai_cnt[ 1 ] - 1 ) / 2;
bai_cnt[ 1 ] += sign;
ans += 1LL * mu[ 1 ] * bai_cnt[ 1 ] * ( bai_cnt[ 1 ] - 1 ) / 2;
if( A[ idx ] > 1 ){
queue< tuple< int, int > > que;
que.emplace( 1, 0 );
while( not que.empty() ){
int v, t; tie( v, t ) = que.front(); que.pop();
if( A[ idx ] % ( 1LL * v * pf[ A[ idx ] ][ t ] ) == 0 ){
int nv = v * pf[ A[ idx ] ][ t ];
ans -= 1LL * mu[ nv ] * bai_cnt[ nv ] * ( bai_cnt[ nv ] - 1 ) / 2;
bai_cnt[ nv ] += sign;
ans += 1LL * mu[ nv ] * bai_cnt[ nv ] * ( bai_cnt[ nv ] - 1 ) / 2;
que.emplace( nv, t );
}
if( t + 1 < pf[ A[ idx ] ].size() ){
que.emplace( v, t + 1 );
}
}
}
in_shelf[ idx ] ^= 1;
cout << ans << "\n";
}
return 0;
}
```