結果

問題 No.2207 pCr検査
ユーザー zaichu
提出日時 2023-02-05 10:52:54
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,232 bytes
コンパイル時間 24,043 ms
コンパイル使用メモリ 380,896 KB
実行使用メモリ 8,860 KB
最終ジャッジ日時 2024-07-04 01:48:50
合計ジャッジ時間 19,886 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 2
other WA * 1 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff #

use std::collections::HashMap;

fn main() {
    let n = read_input();
    let factorization = factorize(n);
    let mut p_candidates = HashMap::new();

    for (p, e) in factorization.iter() {
        for i in 0..=*e {
            let c = comb(*p as i64, i as i64);
            *p_candidates.entry(c).or_insert(0) += 1;
        }
    }

    for (p, e) in factorization.iter() {
        if p_candidates.contains_key(p) && *p_candidates.get(p).unwrap() == *e as usize {
            println!("{} {}", p, e);
            return;
        }
    }

    println!("-1 -1");
}

fn read_input() -> i64 {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    let n = input.trim().parse::<i64>().unwrap();
    n
}

fn factorize(n: i64) -> HashMap<i64, i64> {
    let mut factorization = HashMap::new();
    let mut n = n;

    for i in 2.. {
        if n == 1 {
            break;
        }

        if n % i == 0 {
            *factorization.entry(i as i64).or_insert(0) += 1;
            n /= i;
        }
    }

    factorization
}

fn comb(n: i64, r: i64) -> i64 {
    if r > n {
        return 0;
    }

    let mut res = 1;

    for i in 0..r {
        res = res * (n - i) / (i + 1);
    }

    res
}
0