[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;  
}  
�