Difficulty
Medium
Problem
Solution
Lets define an array div where div_i is equal to the number of pairs of elements in the array having gcd divisible by i. To find div_i we firstly find the number of elements in the array that are divisible by i, let’s say cnt_i, then it is obvious that div_i = cnt_i \cdot (cnt_i -1 )/2.
Now we define another array dp where dp_i is equal to the number of pairs of elements in the array having gcd equal to i. How to find the value of dp_i? We can say that the number of pairs having gcd equal to i will be equal to the number of pairs having gcd divisible by i minus pairs having gcd equal to some multiple of i (like 2\cdot i, 3\cdot i …). So on this basis we get the following relation
dp_i = div_i - \sum_{j=2}^{i\cdot j \leq 2\cdot 10^6}dp_{i\cdot j}
Our answer will be the smallest i having dp_i = 0.
Time complexity
O(NlogN) where N is the upper limit of the elements in the array.
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
cin>>n;
const int N=2e6;
vector<ll>cnt(N+1);
vector<ll>div(N+1);
for(int i=0; i<n; i++){
int num;
cin>>num;
cnt[num]++;
}
for(int i=1; i<=N; i++){
for(int j=2; i*j<=N; j++)
cnt[i]+=cnt[i*j];
}
for(int i=1; i<=N; i++){
div[i]=cnt[i]*(cnt[i]-1)/2;
}
vector<ll>dp(N+1);
for(int i=N; i>=1; i--){
dp[i]=div[i];
for(int j=2; i*j<=N; j++)
dp[i]-=dp[i*j];
}
for(int i=1; i<=N; i++){
if(dp[i]==0){
cout<<i;
return 0;
}
}
cout<<N+1;
return 0;
}