結果

問題 No.2829 GCD Divination
コンテスト
ユーザー テナガザル
提出日時 2024-08-02 21:48:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 476 bytes
コンパイル時間 943 ms
コンパイル使用メモリ 96,216 KB
実行使用メモリ 88,224 KB
最終ジャッジ日時 2024-08-02 21:48:21
合計ジャッジ時間 6,211 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int n;
  cin >> n;
  vector<double> dp(n + 1, -1);
  dp[0] = dp[1] = 0;
  auto dfs = [&](auto f, int now) -> double
  {
    if (dp[now] != -1) return dp[now];
    double sum = 0;
    for (int i = 1; i < now; ++i)
    {
      int nxt = __gcd(i, now);
      sum += f(f, nxt);
    }
    dp[now] = (sum + now) / (now - 1);
    return dp[now];
  };
  printf("%.10f\n", dfs(dfs, n));
}
0