結果

問題 No.2829 GCD Divination
コンテスト
ユーザー northward
提出日時 2024-08-02 22:38:31
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
TLE  
実行時間 -
コード長 761 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,633 ms
コンパイル使用メモリ 191,240 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-03 19:40:15
合計ジャッジ時間 24,574 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 34 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![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