結果

問題 No.811 約数の個数の最大化
ユーザー MiyamonYMiyamonY
提出日時 2019-04-13 11:04:29
言語 Rust
(1.77.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,947 bytes
コンパイル時間 14,500 ms
コンパイル使用メモリ 379,656 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 06:59:49
合計ジャッジ時間 27,604 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 TLE -
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 5 ms
5,376 KB
testcase_06 AC 34 ms
5,376 KB
testcase_07 AC 65 ms
5,376 KB
testcase_08 AC 708 ms
5,376 KB
testcase_09 AC 767 ms
5,376 KB
testcase_10 AC 370 ms
5,376 KB
testcase_11 TLE -
testcase_12 AC 255 ms
5,376 KB
testcase_13 TLE -
testcase_14 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashMap;

#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    (;;$n:expr) => {
        {
            (0..$n).map(|_| scan!()).collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let (n, k) = scan!(usize, i64);

    let mut m = n;
    let mut map = HashMap::new();
    for i in 2.. {
        while m % i == 0 {
            m /= i;
            *map.entry(i).or_insert(0) += 1;
        }
        if m == 1 {
            break;
        }
    }

    let mut candidates = (1..n)
        .map(|i| {
            let mut m = i;
            let mut map0 = HashMap::new();
            for j in 2.. {
                while m % j == 0 {
                    m /= j;
                    *map0.entry(j).or_insert(0) += 1;
                }
                if m == 1 {
                    break;
                }
            }
            let mut same = 0;
            for (key, num) in &map {
                same += num.min(map0.get(&key).unwrap_or(&0));
            }
            (same, map0.iter().fold(1, |s, (_, num)| s * (num + 1)), i)
        })
        .filter(|&(same, _, _)| same >= k)
        .collect::<Vec<_>>();

    candidates.sort_by_key(|(_, k, _)| -k);
    let m = candidates[0].1;

    println!(
        "{}",
        candidates
            .iter()
            .filter(|&(_, k, _)| *k == m)
            .min_by_key(|(_, _, n)| n)
            .unwrap()
            .2
    )
}
0