結果
問題 | No.2829 GCD Divination |
ユーザー | pitP |
提出日時 | 2024-08-02 22:51:07 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,188 bytes |
コンパイル時間 | 6,472 ms |
コンパイル使用メモリ | 337,304 KB |
実行使用メモリ | 200,344 KB |
最終ジャッジ日時 | 2024-08-02 22:51:51 |
合計ジャッジ時間 | 40,567 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 797 ms
200,160 KB |
testcase_01 | AC | 798 ms
200,184 KB |
testcase_02 | AC | 979 ms
199,972 KB |
testcase_03 | AC | 816 ms
200,196 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 802 ms
200,136 KB |
testcase_12 | WA | - |
testcase_13 | AC | 920 ms
200,072 KB |
testcase_14 | AC | 879 ms
200,116 KB |
testcase_15 | WA | - |
testcase_16 | AC | 791 ms
200,196 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 788 ms
200,124 KB |
testcase_21 | WA | - |
testcase_22 | AC | 823 ms
200,124 KB |
testcase_23 | WA | - |
testcase_24 | AC | 945 ms
200,192 KB |
testcase_25 | AC | 978 ms
200,176 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 898 ms
200,012 KB |
testcase_30 | WA | - |
testcase_31 | AC | 826 ms
200,192 KB |
testcase_32 | AC | 886 ms
200,008 KB |
testcase_33 | WA | - |
testcase_34 | WA | - |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); } istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } typedef long long ll; typedef vector<vector<int>> Graph; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define FOR(i,l,r) for (int i = l;i < (int)(r); i++) #define rep(i,n) for (int i = 0;i < (int)(n); i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define my_sort(x) sort(x.begin(), x.end()) #define my_max(x) *max_element(all(x)) #define my_min(x) *min_element(all(x)) template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int INF = (1<<30) - 1; const ll LINF = (1LL<<62) - 1; const int MOD = 998244353; const int MOD2 = 1e9+7; const double PI = acos(-1); vector<int> di = {1,0,-1,0}; vector<int> dj = {0,1,0,-1}; #ifdef LOCAL # include <debug_print.hpp> # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast<void>(0)) #endif // https://qiita.com/drken/items/3beb679e54266f20ab63 struct Eratosthenes{ int N; vector<bool> isprime; vector<int> minfactor, mobius; Eratosthenes(int N_max = 1e7){init(N_max);} //初期化 void init(int N_max = 1e7){ int N = N_max; isprime.assign(N+1,true); minfactor.assign(N+1,-1); mobius.assign(N+1,1); //Eratosthenes O(NloglogN) isprime[0] = false; isprime[1] = false; for(int p=2;p<=N;p++){ if (!isprime[p])continue; minfactor[p] = p; mobius[p] = -1; //pの倍数の処理 for(int q=2*p;q<=N;q+=p){ isprime[q] = false; if (minfactor[q] == -1){ minfactor[q] = p; } if ((q/p) % p == 0) mobius[q] = 0; else mobius[q] *= -1; } } } //素数判定,O(1) bool judge_prime(int num){ return isprime[num]; } //素数列挙,O(N) vector<int> list_primes(int num = -1){ if (num == -1) num = N; vector<int> primes; for(int p=0;p<=num;p++){ if (isprime[p]) primes.push_back(p); } return primes; } //高速素因数分解,O(logN),{(素因数,個数)...} vector<pii> factorize(int x){ vector<pii> ans; while(x > 1){ int p = minfactor[x]; int e = 0; while(minfactor[x] == p){ x /= p; e++; } ans.push_back(make_pair(p,e)); } return ans; } //高速約数列挙 O(240(N <= 1e6),1344(N <= 1e9)) vector<int> divisors(int x){ vector<int> ans; ans.push_back(1); vector<pii> facts = factorize(x); for(auto [p,e]:facts){ int s = ans.size(); for(int i=0;i<s;i++){ int v = 1; for(int j=0;j<e;j++){ v *= p; ans.push_back(ans[i] * v); } } } sort(all(ans)); return ans; } //オイラーのphi関数 ll euler_phi(int x){ auto facts = factorize(x); ll res = x; for(auto [p, e]:facts){ res = res - res / p; } return res; } //メビウス関数 //mobius[1] = 1 //nが素数pで2回以上割り切れる -> mobius[n] = 0 //mobius[n] = pow(-1,Nの素数の種類) int my_mobius(int x){ return mobius[x]; } }; // f -> F, 累積和Fを求める template<typename T> vector<T> fast_zeta(vector<T> &f){ vector<T> res = f; int N = f.size() - 1; Eratosthenes er(N); for(int p=2;p<=N;p++){ if (!er.judge_prime(p)) continue; for(int k=(N/p);k>0;k--){ res[k] += res[k * p]; } } return res; } // // F -> f, 累積和Fを分解する // template<typename T> // vector<T> fast_mobius(vector<T> &F){ // vector<T> res = F; // int N = F.size() - 1; // Eratosthenes er(N); // for(int p=2;p<=N;p++){ // if (!er.judge_prime(p)) continue; // for(int k=1;k<=(N/p);k++){ // res[k] -= res[k * p]; // } // } // return res; // } template<typename T> vector<T> gcd_conv(vector<T> &f, vector<T> &g){ int N = max(f.size(), g.size()); vector<T> F(N+1) , G(N+1), H(N+1); for(int i=0;i<f.size();i++){ F[i] = f[i]; } for(int i=0;i<g.size();i++){ G[i] = g[i]; } F = fast_zeta(F); G = fast_zeta(G); for(int i=1;i<=N;i++){ H[i] = F[i] * G[i]; } H = fast_mobius(H); return H; } const int L = 1e7; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); Eratosthenes er(L); vector<int> F(L + 1); auto fast_mobius = [&](int N){ for(int p=2;p<=N;p++){ if (!er.judge_prime(p)) continue; for(int k=1;k<=(N/p);k++){ F[k] -= F[k * p]; } } }; vector<double> memo(L + 1, -1); memo[1] = 0.0; function<double(int)> dp = [&](int x){ if(memo[x] >= 0.0) return memo[x]; auto divs = er.divisors(x); for(auto &M : divs) F[M] = x / M; fast_mobius(x); double acc = 0.0; for(auto &M : divs) { if(M == x || M == 1) continue; acc += (double)F[M] * dp(M); } memo[x] = (acc + (double)x) / (double)(x - 1); return memo[x]; }; int N; cin >> N; cout << fixed << setprecision(15) << dp(N) << endl; }