結果

問題 No.2829 GCD Divination
ユーザー naut3
提出日時 2024-08-02 22:38:31
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 761 bytes
コンパイル時間 12,974 ms
コンパイル使用メモリ 383,536 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-08-02 22:39:05
合計ジャッジ時間 18,441 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case)]
#[allow(unused_imports)]
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
    input! {
        N: usize,
    }

    let mut buffer = vec![0.0; 10_000_010];

    solve(N, &mut buffer);

    println!("{}", buffer[N]);
}

fn solve(m: usize, buffer: &mut [f64]) {
    if m == 1 {
        return;
    }

    let mut w = 0.;

    for i in 1..m {
        let g = gcd(i, m);

        if buffer[g] == 0. && g != 1 {
            solve(g, buffer);
        }

        w += buffer[g];
    }

    buffer[m] = w / (m - 1) as f64 + m as f64 / (m - 1) as f64;
}

fn gcd(a: usize, b: usize) -> usize {
    if a < b {
        return gcd(b, a);
    }

    if b == 0 {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
0