Nasser's GCD Partners#12480

Nasser's GCD Partners (Editorial)

Problem Author:	Mohammad Nasser (MOAGEZA)
Prepared by:	Mohammad Nasser (MOAGEZA)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea: We need to find the maximum length subsequence where every element shares a $g cd > 1$ \gcd > 1 with at least one other element.

Key Observation:

Two elements share a $g cd > 1$ \gcd > 1 if and only if they share at least one common prime factor.

So an element can be included in the subsequence if and only if at least one of its prime factors appears in at least $2$ elements of the array (so it has a valid partner).

Algorithm:

Precompute the Smallest Prime Factor (SPF) for all numbers up to $1 0^{6}$ 10^6 using a sieve.
For each element $a_{i}$ a_i, factorize it using SPF and count the frequency of each prime factor across all elements.
For each element $a_{i}$ a_i, check if any of its prime factors has frequency $\geq 2$ . If yes, include it in the answer.

Why this works:

Elements equal to $1$ are always excluded since $g cd (1, x) = 1$ \gcd(1, x) = 1 for all $x$ .
If a prime $p$ appears in at least $2$ elements, all elements divisible by $p$ can be partners with each other.
If all prime factors of an element appear in only $1$ element (itself), it has no valid partner and must be excluded.

Complexity Analysis:

Sieve precomputation: $O (N lo g lo g N)$ \mathcal{O}(N \log \log N) where $N = 1 0^{6}$ N = 10^6.

Per test case: $O (n lo g n)$ \mathcal{O}(n \log n) for factorization using SPF.

#include <bits/stdc++.h>
using namespace std;

const int MAXA = 1e6 + 5;
int spf[MAXA];

void precompute() {
    for (int i = 1; i < MAXA; i++) spf[i] = i;
    for (int i = 2; i * i < MAXA; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j < MAXA; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> freq(n + 1, 0);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int temp = a[i];
        while (temp > 1) {
            int p = spf[temp];
            freq[p]++;
            while (temp % p == 0) temp /= p;
        }
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 1) continue;
        
        int temp = a[i];
        bool can_include = false;
        
        while (temp > 1) {
            int p = spf[temp];
            if (freq[p] >= 2) {
                can_include = true;
                break;
            }
            while (temp % p == 0) temp /= p;
        }
        
        if (can_include) ans++;
    }
    
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    precompute();
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}