結果
問題 | No.2829 GCD Divination |
ユーザー | rieaaddlreiuu |
提出日時 | 2024-12-04 20:28:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,619 bytes |
コンパイル時間 | 1,825 ms |
コンパイル使用メモリ | 175,252 KB |
実行使用メモリ | 557,024 KB |
最終ジャッジ日時 | 2024-12-04 20:29:12 |
合計ジャッジ時間 | 56,098 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,624 KB |
testcase_01 | MLE | - |
testcase_02 | AC | 122 ms
166,944 KB |
testcase_03 | AC | 2 ms
481,664 KB |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | AC | 9 ms
16,652 KB |
testcase_12 | AC | 1,101 ms
341,220 KB |
testcase_13 | AC | 1,243 ms
357,512 KB |
testcase_14 | AC | 852 ms
496,736 KB |
testcase_15 | TLE | - |
testcase_16 | AC | 119 ms
410,348 KB |
testcase_17 | AC | 540 ms
68,740 KB |
testcase_18 | AC | 118 ms
412,632 KB |
testcase_19 | AC | 181 ms
86,608 KB |
testcase_20 | AC | 3 ms
401,224 KB |
testcase_21 | TLE | - |
testcase_22 | AC | 53 ms
511,436 KB |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | AC | 1,353 ms
387,284 KB |
testcase_26 | AC | 1,002 ms
194,352 KB |
testcase_27 | TLE | - |
testcase_28 | AC | 187 ms
72,836 KB |
testcase_29 | AC | 599 ms
175,264 KB |
testcase_30 | TLE | - |
testcase_31 | AC | 34 ms
38,048 KB |
testcase_32 | AC | 179 ms
173,400 KB |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
ソースコード
#include<bits/stdc++.h>using namespace std;// 素因数分解を行い、(素因数, 指数)のペアを返す関数vector<pair<int, int>> primeFactorization(int n) {vector<pair<int, int>> factors;// 2で割り切れる限り割るint count = 0;while (n % 2 == 0) {count++;n /= 2;}if (count > 0) {factors.push_back({2, count});}// 3以上の奇数で割り切れる限り割るfor (int i = 3; i * i <= n; i += 2) {count = 0;while (n % i == 0) {count++;n /= i;}if (count > 0) {factors.push_back({i, count});}}// nが素数の場合(1より大きい)if (n > 1) {factors.push_back({n, 1});}return factors;}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(int n, const vector<pair<int, int>>& factors) {double result = n; // 初期値をnに設定for (const auto& factor : factors) {int p = factor.first; // 素因数if(factor.second != 0){result *= (1.0 - 1.0 / p);}}return static_cast<int>(result); // 結果を整数に変換}double fill_dp(const 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;while(e[size-1] <= factors[size-1].second){for(int i=0;i<size;i++){k[i].first = factors[i].first;k[i].second = e[i];n_k[i].first = factors[i].first;n_k[i].second = factors[i].second - e[i];}k_num = reconstructFromFactors(k);if(k_num != n){sum_dp += (double)computeTotient(reconstructFromFactors(n_k),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]++;}}}dp[n] = ((double)n + sum_dp)/((double)(n-1));return dp[n];}int main() {int N;cin >> N;vector<pair<int,int>> factors = primeFactorization(N);vector<double> dp(N+1,-1.0);dp[1] = 1;cout << fill_dp(factors,dp) << endl;return 0;}