結果

問題 No.2829 GCD Divination
ユーザー 4094706840947068
提出日時 2024-08-02 22:28:07
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,561 ms / 2,000 ms
コード長 4,904 bytes
コンパイル時間 2,640 ms
コンパイル使用メモリ 159,548 KB
実行使用メモリ 160,896 KB
最終ジャッジ日時 2024-09-26 01:27:05
合計ジャッジ時間 27,696 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1,538 ms
160,896 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1,537 ms
160,896 KB
testcase_05 AC 1,561 ms
140,288 KB
testcase_06 AC 1,284 ms
117,504 KB
testcase_07 AC 1,117 ms
106,240 KB
testcase_08 AC 756 ms
71,936 KB
testcase_09 AC 617 ms
60,544 KB
testcase_10 AC 817 ms
91,248 KB
testcase_11 AC 20 ms
7,296 KB
testcase_12 AC 212 ms
31,868 KB
testcase_13 AC 1,361 ms
143,872 KB
testcase_14 AC 867 ms
98,048 KB
testcase_15 AC 607 ms
71,296 KB
testcase_16 AC 241 ms
35,328 KB
testcase_17 AC 91 ms
20,864 KB
testcase_18 AC 66 ms
15,872 KB
testcase_19 AC 130 ms
25,856 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 487 ms
60,544 KB
testcase_22 AC 611 ms
72,208 KB
testcase_23 AC 744 ms
85,120 KB
testcase_24 AC 1,220 ms
127,360 KB
testcase_25 AC 1,490 ms
155,904 KB
testcase_26 AC 568 ms
67,712 KB
testcase_27 AC 1,077 ms
116,480 KB
testcase_28 AC 150 ms
26,748 KB
testcase_29 AC 634 ms
72,576 KB
testcase_30 AC 1,452 ms
149,980 KB
testcase_31 AC 92 ms
20,896 KB
testcase_32 AC 777 ms
89,088 KB
testcase_33 AC 554 ms
64,768 KB
testcase_34 AC 1,074 ms
116,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<sstream>
#include<algorithm>
#include<deque>
#include<list>
#include<map>
#include<memory>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<string.h>
#include<string>
#include<math.h>
#include<float.h>
#include<stdio.h>
#include<vector>
#include<iomanip>
#include<bitset>
//#include<random>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T &a, T b) { return ((a>b) ? (a = b, true) : (false));}
#define rep(i,s,n) for(long long i=s;i<(long long)(n);i++)
#define rrep(i,s,n) for(long long i=n-1;i>=s;i--)
const long long inf = 1LL<<60;
typedef long long ll;
typedef long double ld;
#define cmp [](pair<ll,ll> a, pair<ll,ll> b){return a.second<b.second;} //pairのsecondでソートsort(p.begin(),p.end(),cmp)
typedef pair<long long, long long> P;
typedef pair<ll, pair<ll,ll> > PP;
#define rll ll,vector<ll>,greater<ll>
#define rP P,vector<P>,greater<P>
const long double pi = 3.14159265358979;
typedef unsigned long long ull;
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vvch vector<vector<char>>
#define vch vector<char>
#define rPP PP,vector<PP>,greater<PP>
#define vP vector<P> 
#define vvP vector<vector<P>>
#define all(x) x.begin(), x.end()
//bitの差集合 S & ~(1<<i)
//UNIQUE(x) xをソートして値の被りがないようにする
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())


// エラトステネスの篩
struct Eratosthenes {
    // テーブル
    vector<bool> isprime;
    
    // 整数 i を割り切る最小の素数
    vector<ll> minfactor;

    //メビウス関数
    //約数系包除に使用する
    //mobius[n] := nに同じ素因数が複数個ある => 0,  nの素因数が奇数個 => -1, 素因数が偶数個 => 1
    vector<ll> mobius;

    // コンストラクタで篩を回す
    Eratosthenes(ll N) : isprime(N+1, true),
                          minfactor(N+1, -1),
                          mobius(N+1, 1) {
        // 1 は予めふるい落としておく
        isprime[1] = false;
        minfactor[1] = 1;

        // 篩
        for (ll p = 2; p <= N; ++p) {
            // すでに合成数であるものはスキップする
            if (!isprime[p]) continue;

            // p についての情報更新
            minfactor[p] = p;
            mobius[p] = -1;
            
            // p 以外の p の倍数から素数ラベルを剥奪
            for (ll q = p * 2; q <= N; q += p) {
                // q は合成数なのでふるい落とす
                isprime[q] = false;
                
                // q は p で割り切れる旨を更新
                if (minfactor[q] == -1) minfactor[q] = p;
                if((q/p) % p == 0) mobius[q] = 0;
                else mobius[q] = -mobius[q];
            }
        }
    }

    // 高速素因数分解
    // pair (素因子, 指数) の vector を返す
    vector<P> factorize(ll n) {
        vector<P> res;
        while (n > 1) {
            ll p = minfactor[n];
            ll exp = 0;

            // n で割り切れる限り割る
            while (minfactor[n] == p) {
                n /= p;
                ++exp;
            }
            res.emplace_back(p, exp);
        }
        return res;
    }

    // 高速約数列挙
    vector<ll> divisors(ll n) {
        vector<ll> res({1});

        // n を素因数分解 (メンバ関数使用)
        auto pf = factorize(n);

        // 約数列挙
        for (auto p : pf) {
            ll s = (ll)res.size();
            for (ll i = 0; i < s; ++i) {
                ll v = 1;
                for (ll j = 0; j < p.second; ++j) {
                    v *= p.first;
                    res.push_back(res[i] * v);
                }
            }
        }
        return res;
    }
};

int main()
{
    ll n; cin >> n;
    Eratosthenes er(n+1);
    
    map<ll, ld> dp;
    dp[1] = 0;
    //nの約数のみを考えればよく、単純に昇順でいい
    auto divisors = er.divisors(n);
    sort(all(divisors));

    for(auto divisor : divisors) {
        if(divisor == 1) continue;
        auto sub_divisors = er.divisors(divisor); //divisorとのgcdについて全探索?
        sort(all(sub_divisors)); reverse(all(sub_divisors));

        map<ll,ld> cnt; //gcdがsub_divisorとなるものの数
        for(auto sub_divisor : sub_divisors) {
            cnt[sub_divisor] = divisor / sub_divisor;
            for(auto p : divisors) {
                if(p == 1) continue;
                if(p * sub_divisor > divisor) break;
                cnt[sub_divisor] -= cnt[p * sub_divisor];
            }
        }

        ld sum = divisor;
        for(auto p : cnt) sum += dp[p.first] * p.second;
        dp[divisor] = sum / (ld)(divisor - 1);
    }
    cout << setprecision(30) << dp[n] << endl;
}
0