[Codeforces] E. Mike and Foam

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Mike and Foam
Source            : Codeforces
Category          : Number Theory
Algorithm         : Mobius Function
Verdict           : Accepted

Tutorial : https://artofproblemsolving.com/wiki/index.php/Mobius_function

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll               long long int  
#define endl             '\n'  
  
static const int maxn = 5e5 + 5;  
  
bool isprime[maxn];  
vector <int> prime;  
vector <int> divisor[maxn];  
  
void seive()  
{  
      for (int i = 1; i < maxn; i++)  
      {  
            divisor[i].push_back(1);  
            isprime[i] = true;  
      }  
      for (int i = 2; i < maxn; i++)  
      {  
            if (isprime[i]) prime.push_back(i);  
            for (int j = 1; i * j < maxn; j++)  
            {  
                  isprime[i * j] = false;  
                  divisor[i * j].push_back(i);  
            }  
      }  
}  
  
int mobius[maxn];  
  
void calc_mobius()  
{  
      for (int i = 1; i < maxn; i++) mobius[i] = 1;  
      for (int p : prime)  
      {  
            int x = p * p;  
            if (x >= maxn) break;  
            for (int j = x; j < maxn; j += x) mobius[j] = 0;  
      }  
      for (int p : prime)  
            for (int j = p; j < maxn; j += p) mobius[j] *= -1;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      seive();  
      calc_mobius();  
      int n, q;  
      cin >> n >> q;  
      vector <int> arr(n + 1);  
      vector <bool> in_self(maxn);  
      vector <int> div_count(maxn);  
      for (int i = 1; i <= n; i++) cin >> arr[i];  
      ll ans = 0;  
      while (q--)  
      {  
            int pos;  
            cin >> pos;  
            int x = arr[pos];  
            if (in_self[pos] == 0)  
            {  
                  in_self[pos] = 1;  
                  for (int d : divisor[x])  
                  {  
                        ans += 1LL * mobius[d] * div_count[d];  
                        div_count[d] += 1;  
                  }  
            }  
            else  
            {  
                  in_self[pos] = 0;  
                  for (int d : divisor[x])  
                  {  
                        div_count[d] -= 1;  
                        ans -= 1LL * mobius[d] * div_count[d];  
                  }  
            }  
            cout << ans << endl;  
      }  
}