Koasar and PGCD#12431

Koasar and PGCD (Розбір)

Автор задачі:	Al Koasar Hussain (Al_Kaosar)
Підготував:	Mohammad Nasser (MOAGEZA)
Редактор:	Hasan Saleh (MathModel)

Розв'язання

Загальна ідея: Потрібно з'ясувати, чи існує додатне ціле число $d$ таке, що $g cd (a_{i}, a_{j}) = g$ \gcd(a_i, a_j) = g для всіх пар в арифметичній послідовності.

Спочатку перевіримо, чи ділиться $a$ на $g$ . Якщо ні, це неможливо.

Якщо $a = g$ a = g, то відповідь завжди "YES", оскільки ми можемо вибрати будь-яке $d$ , кратне $g$ .

Інакше нехай $x = a / g$ x = a / g. Ключове спостереження таке:

Якщо $x$ має простий дільник $p$ і $m > p$ m > p, то ми не зможемо уникнути появи пар із $g cd > g$ \gcd > g.
Якщо $m \leq p$ m \le p, де $p$ — найменший простий дільник числа $x$ , ми можемо вибрати $d = g$ d = g, і умова виконуватиметься.

Отже, потрібно знайти найменший простий дільник числа $x$ і перевірити, чи не перевищує $m$ це значення.

Розв'язок працює за $O (x)$ \mathcal{O}(\sqrt{x}) на один набір вхідних даних.

#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;
}