結果
問題 |
No.2829 GCD Divination
|
ユーザー |
![]() |
提出日時 | 2024-12-04 21:05:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,976 bytes |
コンパイル時間 | 1,918 ms |
コンパイル使用メモリ | 176,408 KB |
実行使用メモリ | 555,708 KB |
最終ジャッジ日時 | 2024-12-04 21:06:21 |
合計ジャッジ時間 | 55,922 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 19 TLE * 15 MLE * 1 |
ソースコード
#include<bits/stdc++.h> using namespace std; // 素因数分解を行い、(素因数, 指数)のペアを返す関数 vector<pair<int, int>> primeFactorization(int N) { vector<pair<int,int> > res; // √N まで試し割っていく for (long long p = 2; p * p <= N; ++p) { // N が p で割り切れないならばスキップ if (N % p != 0) { continue; } // N の素因数 p に対する指数を求める int e = 0; while (N % p == 0) { // 指数を 1 増やす ++e; // N を p で割る N /= p; } // 答えに追加 res.emplace_back(p, e); } // 素数が最後に残ることがありうる if (N != 1) { res.emplace_back(N, 1); } return res; } int reconstructFromFactors(const vector<pair<int, int>>& factors) { int result = 1; for (const auto& factor : factors) { result *= (int)pow(factor.first, factor.second); } return result; } int computeTotient(const vector<pair<int, int>>& factors) { double result = 1.0; // 初期値をnに設定 for (const auto& factor : factors) { int p = factor.first; // 素因数 if(factor.second != 0){ result *= pow(factor.first,factor.second)*(1.0 - 1.0 / p); } } return static_cast<int>(result); // 結果を整数に変換 } double fill_dp(vector<pair<int,int>> factors,vector<double> dp){ int n = reconstructFromFactors(factors); if(dp[n] > -0.5){ return dp[n]; } int size = factors.size(); double sum_dp = 0.0; vector<int> e(size,0); vector<pair<int,int>> k(size); vector<pair<int,int>> n_k(size); int k_num; e[0] = 1; for(int i=0;i<size;i++){ k[i].first = factors[i].first; n_k[i].first = factors[i].first; k[i].second = e[i]; n_k[i].second = factors[i].second - e[i]; } while(e[size-1] <= factors[size-1].second){ k_num = reconstructFromFactors(k); if(k_num != n){ sum_dp += (double)computeTotient(n_k) * fill_dp(k,dp); } e[0]++; for(int i=0;i<size-1;i++){ if(e[i] > factors[i].second){ e[i] = 0; e[i+1]++; } k[i].second = e[i]; n_k[i].second = factors[i].second - e[i]; } k[size-1].second = e[size-1]; n_k[size-1].second = factors[size-1].second - e[size-1]; } dp[n] = ((double)n + sum_dp)/((double)(n-1)); return dp[n]; } int main() { int N; cin >> N; clock_t start = clock(); vector<pair<int,int>> factors = primeFactorization(N); vector<double> dp(N+1,-1.0); dp[1] = 1; cout << fill_dp(factors,dp) << endl; clock_t end = clock(); const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0; printf("time %lf[ms]\n", time); return 0; }