結果

問題 No.2829 GCD Divination
コンテスト
ユーザー nana
提出日時 2024-08-02 21:56:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,809 bytes
コンパイル時間 1,680 ms
コンパイル使用メモリ 135,416 KB
最終ジャッジ日時 2025-02-23 20:02:04
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

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;
        //cout << divisor << endl;
        auto sub_divisors = er.divisors(divisor); //divisorとのgcdについて全探索?
        sort(all(sub_divisors)); reverse(all(sub_divisors));

        map<ll,ll> cnt; //gcdがkeyとなるものの数
        for(auto sub_divisor : sub_divisors) {
            cnt[sub_divisor] = n / sub_divisor;
            for(ll p=sub_divisor*2;p<=n;p+=sub_divisor) cnt[sub_divisor] -= cnt[p];
        }

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