結果

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

ソースコード

diff #
raw source code 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        ll n, k;
        cin >> n >> k;

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

        // Start from n and go down
        ll curr = n;
        while (true) {
            if (curr == k) {
                cout << "-1\n";
                break;
            }

            bool good = true;
            // Check if curr has any small factor <= k
            for (ll i = 2; i * i <= curr; i++) {
                if (curr % i == 0) {
                    // Found a small factor ? not good
                    good = false;
                    break;
                }
            }

            if (good) {
                // curr is either prime or has large prime factor (> sqrt(curr) > k possibly)
                // But we need largest prime factor > k
                // So better: just compute largest prime factor directly
                ll lpf = 0;
                ll x = curr;
                while (x % 2 == 0) { lpf = 2; x /= 2; }
                for (ll i = 3; i * i <= x; i += 2) {
                    while (x % i == 0) { lpf = i; x /= i; }
                }
                if (x > 1) lpf = x;

                if (lpf > k) {
                    cout << curr << "\n";
                    break;
                }
            }
            curr--;
        }
    }
    return 0;
}
0