[Codeforces] F. Make It One

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : F. Make It One
Source            : Codeforces
Category          : Number Theroy
Algorithm         : Mobius Function 
Verdict           : Accepted


#include "bits/stdc++.h"  
  
#define ll          long long int  
#define endl        '\n'  
  
using namespace std;  
  
static const int maxn = 3e5 + 5;  
static const long long mod = 1e9 + 7;  
  
int fre[maxn];  
int divi[maxn];  
bool isprime[maxn];  
vector <int> prime;  
  
void seive()  
{  
      for (int i = 2; i < maxn; i++) isprime[i] = true;  
      for (int i = 2; i < maxn; i++)  
      {  
            if (isprime[i]) prime.push_back(i);  
            for (int j = 1; 1LL * i * j < maxn; j++)  
            {  
                  isprime[i * j] = false;  
                  divi[i] += fre[i * j];  
            }  
      }  
}  
  
int mobius[maxn];  
  
void calc_mobius()  
{  
      for (int i = 1; i < maxn; i++) mobius[i] = 1;  
      for (int p : prime)  
      {  
            if (1LL * p * p > maxn) break;  
            int x = p * p;  
            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;  
      }  
}  
  
long long binaryExpo(long long a, long long p, long long m)  
{  
      if (p == 0) return 1 % m;  
      if (p == 1) return a % m;  
      if (p & 1) return (a % m * binaryExpo(a, p - 1, m) % m) % m;  
      long long ret = binaryExpo(a, p / 2, m);  
      return (ret % m * ret % m) % m;  
}  
  
long long mod_inv(long long a, long long m)  
{  
      return binaryExpo(a, m - 2, m);  
}  
  
long long fact[maxn];  
long long inv[maxn];  
  
void calc_fact()  
{  
      fact[0] = 1;  
      inv[0] = 1;  
      for (int i = 1; i < maxn; i++)  
      {  
            fact[i] = (1LL * i * fact[i - 1]) % mod;  
            inv[i] = mod_inv(fact[i], mod);  
      }  
}  
  
long long nCr(int n, int r)  
{  
      if (n < r) return 0;  
      if (n == r) return 1;  
      long long nom = fact[n];  
      long long dem = (fact[r] * fact[n - r]) % mod;  
      long long ncr = (nom * mod_inv(dem, mod)) % mod;  
      return ncr;  
}  
  
ll count_coprime(int r)  
{  
      ll coprime = 0;  
      for (int d = 1; d < maxn; d++)  
      {  
            ll ncr = nCr(divi[d], r);  
            coprime += (mobius[d] * ncr + mod) % mod;  
            coprime %= mod;  
      }  
      return coprime;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
  
      int n;  
      cin >> n;  
      for (int i = 1; i <= n; i++)  
      {  
            int x;  
            cin >> x;  
            if (x == 1) return (cout << 1), 0;  
            fre[x]++;  
      }  
      divi[1] = n;  
      seive();  
      calc_mobius();  
      calc_fact();  
      for (int r = 2; r < 10; r++)  
      {  
            ll coprime = count_coprime(r);  
            if (coprime > 0) return (cout << r << endl), 0;  
      }  
      cout << -1 << endl;  
}  
�  

[Codeforces] E. Mike and Foam

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

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 5e5 + 6;  
  
int sp[maxn];  
vector <int> divisor[maxn];  
  
void seive()  
{  
      for (int i = 2; i < maxn; i++) sp[i] = i;  
      for (int i = 2; i < maxn; i++)  
      {  
            for (int j = 1; 1LL * i * j < maxn; j++)  
            {  
                  sp[i * j] = min(sp[i * j], sp[i]);  
                  divisor[i * j].push_back(i);  
            }  
      }  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      seive();  
      int n, q;  
      cin >> n >> q;  
      vector <int> arr(n + 1);  
      for (int i = 1; i <= n; i++) cin >> arr[i];  
      vector <int> in_self(n + 1);  
      int in_self_cnt = 0;  
      vector <int> divi(maxn);  
      auto get = [&](vector <int> &vec)  
      {  
            int n = vec.size();  
            long long coprime = 0;  
            for (int mask = 0; mask < (1 << n); mask++)  
            {  
                  long long d = 1;  
                  int bitCnt = 0;  
                  for (int i = 0; i < n; i++)  
                  {  
                        if ((mask >> i) & 1)  
                        {  
                              d *= vec[i];  
                              bitCnt++;  
                        }  
                  }  
                  if (bitCnt & 1) coprime += divi[d];  
                  else coprime -= divi[d];  
            }  
            return coprime;  
      };  
      long long ans = 0;  
      while (q--)  
      {  
            int pos;  
            cin >> pos;  
            vector <int> prime_factors;  
            int num = arr[pos];  
            while (num > 1)  
            {  
                  int x = sp[num];  
                  prime_factors.push_back(x);  
                  while (num % x == 0) num /= x;  
            }  
            sort(prime_factors.begin(), prime_factors.end());  
            num = arr[pos];  
            if (in_self[pos])  
            {  
                  for (int d : divisor[num]) divi[d]--;  
                  in_self[pos] = 0;  
                  in_self_cnt--;  
                  ans -= in_self_cnt - get(prime_factors);  
            }  
            else  
            {  
                  ans += in_self_cnt - get(prime_factors);  
                  for (int d : divisor[num]) divi[d]++;  
                  in_self[pos] = 1;  
                  in_self_cnt++;  
            }  
            cout << ans << '\n';  
      }  
}