結果

問題 No.2829 GCD Divination
コンテスト
ユーザー ぬるぽ
提出日時 2024-08-02 22:08:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 647 bytes
コンパイル時間 746 ms
コンパイル使用メモリ 84,608 KB
最終ジャッジ日時 2025-02-23 20:03:48
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric> // for std::gcd
#include <unordered_map>

using namespace std;

unordered_map<int, double> memo;

double rec(int n, int N) {
    if (n == 1) {
        return 0;
    }

    if (memo.find(n) != memo.end()) {
        return memo[n];
    }

    double num = 0;
    int cnt = 0;
    for (int M = 1; M <= N; ++M) {
        if (gcd(n, M) == n) {
            cnt += 1;
            continue;
        }
        num += rec(gcd(n, M), N);
    }
    num += N;

    memo[n] = num * 1 / (N - cnt);
    return memo[n];
}

int main() {
    int N;
    cin >> N;
    cout << rec(N, N) << endl;
    return 0;
}
0