結果

問題 No.2 素因数ゲーム
コンテスト
ユーザー srtry
提出日時 2025-09-07 00:40:54
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,496 bytes
コンパイル時間 14,632 ms
コンパイル使用メモリ 404,428 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-07 00:41:11
合計ジャッジ時間 15,591 ms
ジャッジサーバーID
（参考情報） 		judge / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* 
 *     Author:  srtry
 *     Created: 2025-09-06T20:49:42+09:00
 *     Coding:  utf-8-unix
 */

use proconio::input;
use std::collections::{HashMap};
use std::io::{stdout,Write,BufWriter};

fn primes_leq(n:&usize) -> Vec<usize> {
    let n_ = n.clone();
    let mut primes:Vec<usize> = Vec::new();
    let mut is_prime:Vec<bool> = vec![true;n_+1];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..=n_ {
        if is_prime[i] {
            primes.push(i);
            for j in i..=n_/i {
                is_prime[i*j] = false;
            }
        }
    }
    return primes;
}

fn prime_factors(n:&usize) -> HashMap<usize,usize> {
    let mut n_: usize = n.clone();
    let factor_max:usize = (n_ as f32).sqrt() as usize;
    let mut ret:HashMap<usize,usize> = HashMap::new();
    for prime in primes_leq(&factor_max) {
        loop {
            if n_%prime != 0 {
                break;
            }
            ret.entry(prime).and_modify(|e| *e += 1).or_insert(1);
            n_ /= prime;
        }
        if n_==1 {
            return ret
        }
    }
    ret.insert(n_,1);
    return ret
}

fn main() {
    input!{
        n:usize
    }

    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    
    let factors = prime_factors(&n);
    let mut xor:usize = 0;
    for &cnt in factors.values() {
        xor ^= cnt;
    }
    if xor==0 {
        write!(out, "{}", "Bob").unwrap();
    } else {
        write!(out, "{}", "Alice").unwrap();
    }
}
0