Help with CSES problem Common Divisors

Link to the problem: https://cses.fi/problemset/task/1081/
My approach: I came up with an O(n\sqrt{x}) algorithm. I go through each of the numbers and then find their factors using the O(\sqrt{x}) algorithm, and then update the frequency array of the possible factors (with size being equal to the maximum possible number), and then once I have built the frequency array, I go in the reverse order from the largest possible number to 1, and the moment I find that for a factor i, frequency[i] > 1, I stop the traversal. And finally I report the answer as i.
My code:

#include <bits/stdc++.h>
using namespace std;
 
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
const int MAXN = 1e6+5;
vector<int> freq(MAXN,0);
 
void divisors(int x)
{
    for(int i=1; i*i<=x; i++)
    {
        if(x%i == 0)
        {
            if(x/i != i)
            {
                freq[x/i]++;
                freq[i]++;
            }
            else freq[i]++;
        }
    }
}
 
int main()
{
    FASTIO
    int n, maxVal = INT_MIN;
    cin >> n;
    vector<int> arr(n);
    for(int& x : arr) cin >> x, maxVal = max(maxVal, x);
    for(int x : arr) divisors(x);
    for(int i=maxVal; i>=1; i--)
    {
        if(freq[i] > 1)
        {
            cout << i << "\n";
            break;
        }
    }
    return 0;
}

My question: Even though this approach gets an AC, but its still quite slow. Can we do better? If yes (most probably), how can we do it? Are there any other concepts that are needed over here?

Any help is highly appreciated. :slightly_smiling_face:

Sieve Of Eratosthenes method can be used to solve this problem effieciently. Even codechef DSA learning series also covered this topic in youtube. Here is link from geeksforgeeks for quick reference. https://www.geeksforgeeks.org/find-pair-maximum-gcd-array/

1 Like

The answer is the largest number which is a factor of 2 or more numbers.
My code is O(n\log{n}) and runs in 0.04s.

Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
template <class T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
 
void usaco(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(name.size())
    {
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}
 
int main()
{
    usaco();
    int n, x;
    cin >> n;
    vector <int> cnt(1e6+1);
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        ++cnt[x];
    }
    for (int i = 1e6; i; --i)
    {
        int d = 0;
        for (int j = i; j <= 1e6; j += i) d += cnt[j];
        if (d > 1)
        {
            cout << i << '\n';
            return 0;
        }
    }
    cout << 1 << '\n';
}
1 Like

@therealnishuz Can you give the source from where you learnt this approach? :slightly_smiling_face:

1 Like

Not a source, but here


@everule1 sir’s teaching is orz

Actually the third approach on GFG does the same thing (I think so), but does not mention the time complexity. How did you get that time complexity?


Here

Thanks :slightly_smiling_face: .

1 Like