結果

問題 No.3461 Min GCD
コンテスト
ユーザー NakLon131
提出日時 2026-03-04 22:32:03
言語 Rust
(1.93.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 123 ms / 2,000 ms
コード長 1,689 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,659 ms
コンパイル使用メモリ 205,664 KB
実行使用メモリ 19,284 KB
最終ジャッジ日時 2026-03-04 22:32:11
合計ジャッジ時間 6,111 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
use std::cmp::min;
const INF: usize = 1 << 60;
fn main() {
    input! {
        n: usize, // 数列の長さ
        k: usize, // 合計の加算回数の上限
        a: [usize; n], // 数列A
        b: [usize; n], // 数列B
    }

    // 1~10^5の各値について約数列挙を求める
    let mut divs = Vec::new();
    divs.push(vec![0]);

    for i in 1..=1_00_000 {
        let ret = divisor(i);
        divs.push(ret);
    }

    // 答えを二分探索
    let mut ok = 1;
    let mut ng = 1_00_001;

    while ng - ok > 1 {
        let mid = (ng + ok) / 2;
        if check(mid, n, k, &a, &b, &divs) {
            ok = mid;
        }
        else {
            ng = mid;
        }
    }
    println!("{}", ok);
}

fn check(x: usize, n: usize, k: usize, 
    a: &Vec<usize>, b: &Vec<usize>, divs: &Vec<Vec<usize>>) -> bool 
{
    // 加算した回数
    let mut tot_add = 0;

    // 各数字を調べる
    for i in 0..n {
        let mut ret = INF;

        // A[i]の約数について、X以上のものを探す
        for &g in &divs[a[i]] {
            // 必要な加算回数
            if g >= x {
                let diff = (g - (b[i] % g)) % g;
                ret = min(ret, diff);
            }
        }
        if ret == INF {
            return false;
        }

        tot_add += ret;
    }

    tot_add <= k
}



pub fn divisor(n: usize) -> Vec<usize> {
    // 約数列挙
    let mut ret = Vec::new();
    let mut i = 1;
    while i * i <= n {
        if n % i == 0 {
            ret.push(i);
            if n / i != i {
                ret.push(n / i);
            }
        }
        i += 1;
    }
    ret.sort();
    ret
}
0