結果

問題 No.3253 Banned Product
コンテスト
ユーザー vjudge1
提出日時 2025-11-20 22:23:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,547 bytes
コンパイル時間 1,627 ms
コンパイル使用メモリ 198,528 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-20 22:23:25
合計ジャッジ時間 5,855 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define ll long long
#define fast ios::sync_with_stdio(false); cin.tie(nullptr);

vector<int> primes;

// Sieve up to 1e6+10 is enough for trial division
void sieve() {
    const int MAXP = 1000010;
    vector<bool> is_prime(MAXP, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAXP; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAXP; j += i)
                is_prime[j] = false;
        }
    }
    for (int i = 2; i < MAXP; i++)
        if (is_prime[i]) primes.push_back(i);
}

int largest_prime_factor(int n) {
    if (n <= 1) return 0; // important: 1 has no prime factors

    int max_prime = -1;

    // Divide by 2
    while (n % 2 == 0) {
        max_prime = 2;
        n /= 2;
    }

    // Odd factors
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            max_prime = i;
            n /= i;
        }
    }

    if (n > 1) max_prime = n;

    return max_prime;
}

void solve() {
    int n, k;
    cin >> n >> k;

    if (n == k) {
        cout << "-1\n";
        return;
    }

    // Start from n downto 2 (1 is invalid)
    for (int i = n; i >= 2; i--) {
        int lpf = largest_prime_factor(i);
        if (lpf > k) {
            cout << i << "\n";
            return;
        }
    }

    cout << "-1\n";
}

int main() {
    fast
    sieve(); // precompute small primes (optional, but we don't even need primes list now)

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
0