Koasar and PGCD (Editorial)

Solution

General Idea: We need to find if there exists a positive integer $d$ such that \gcd(a_i, a_j) = g for all pairs in the arithmetic sequence.

First, check if $a$ is divisible by $g$. If not, it's impossible.

If a = g, then the answer is always "YES" because we can choose any $d$ that is a multiple of $g$.

Otherwise, let x = a / g. The key observation is:

• If $x$ has a prime factor $p$ and m > p, then we cannot avoid creating pairs with \gcd > g.

• If m \le p where $p$ is the smallest prime factor of $x$, there exists a valid $d$ (specifically one where \gcd(a, d) = g and $d/g$ is a multiple of all primes less than $m$) such that the condition holds.

Therefore, we find the smallest prime factor of $x$ and check if $m$ is at most this value.

The solution runs in \mathcal{O}(\sqrt{x}) time per test case.

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

int smallest_prime_factor(int x) {
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) return i;
    }
    return x;
}

void solve(){
    int a, g, m;
    cin >> a >> g >> m;
    if(m == 1){
        cout << "YES";
        return;
    }
    if (a % g != 0) {
        cout << "NO";
        return;
    }
    
    int x = a / g;
    if (x == 1) {
        cout << "YES";
        return;
    }
    
    int p = smallest_prime_factor(x);
    if (m <= p) cout << "YES";
    else cout << "NO";
}

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