Koasar və PGCD (Həll təhlili)

Həll

Ümumi ideya: Biz elə bir müsbət tam $d$ ədədinin mövcud olub-olmadığını tapmalıyıq ki, arifmetik silsilədə bütün cütlər üçün \gcd(a_i, a_j) = g şərti ödənsin.

Əvvəlcə yoxlayırıq ki, $a$ ədədi $g$-yə bölünürmü. Əgər bölünmürsə, bu mümkün deyil.

Əgər a = g olarsa, cavab həmişə "YES"-dir, çünki $g$-nin istənilən qatını $d$ kimi seçə bilərik.

Əks halda, x = a / g götürək. Əsas müşahidə belədir:

• Əgər $x$ ədədinin hər hansı sadə böləni $p$ varsa və m > p olarsa, onda \gcd > g olan cütlərdən qaçmaq mümkün deyil.

• Əgər m \le p (burada $p$ — $x$-in ən kiçik sadə bölənidir), onda d = g seçərək şərti ödəyə bilərik.

Deməli, $x$-in ən kiçik sadə bölənini tapırıq və yoxlayırıq ki, $m$ bu qiymətdən böyük deyil.

Həllin mürəkkəbliyi hər test halı üçün \mathcal{O}(\sqrt{x})-dir.

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