結果
| 問題 | No.2829 GCD Divination |
| コンテスト | |
| ユーザー |
 irinoirino
|
| 提出日時 | 2026-07-22 11:26:07 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,826 bytes |
| 記録 | |
| コンパイル時間 | 2,448 ms |
| コンパイル使用メモリ | 239,716 KB |
| 実行使用メモリ | 315,904 KB |
| 最終ジャッジ日時 | 2026-07-22 11:26:14 |
| 合計ジャッジ時間 | 5,786 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 2 TLE * 1 -- * 32 |
コンパイルメッセージ
In file included from main.cpp:24:
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/cstdbool:50:6: warning: #warning "<cstdbool> is deprecated in C++17, remove the #include" [-Wcpp]
50 | # warning "<cstdbool> is deprecated in C++17, remove the #include"
| ^~~~~~~
ソースコード
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <tuple>
#include <map>
#include <bit>
#include <array>
#include <limits>
#include <type_traits>
#include <utility>
#include <functional>
#include <fstream>
#include <climits>
#include <numeric>
#include <cassert>
#include <cstdbool>
#include <cstdint>
//#include <atcoder/all>
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define orep(i,n) for(ll i=1;i<=(n);i++)
#define nfor(i,s,n) for(ll i=(s);i<(n);i++)
#define dfor(i,s,n) for(ll i=(s)-1;i>=n;i--)
#define INF 2000000000000000000//9223372036854775807
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define pb push_back
#define pob pop_back
#define vc vector
#define for_sz(s) (long long)(s.size())
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
#define YN {cout << "Yes" << endl;}else{cout << "No" << endl;}
#define dame cout << -1 << endl;
#define vc_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define vc_remove(v,x) v.erase(remove(v.begin(), v.end(),x), v.end())
#define vc_rotate(v) rotate(v.begin(), v.begin()+1, v.end())
#define pop_cnt(s) ll(popcount(uint64_t(s)))
#define next_p(v) next_permutation(v.begin(),v.end())
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
using namespace std;
//using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll,ll>;
using vvvvvl = vector<vector<vector<vector<vector<ll> > > > >;
using vvvvl = vector<vector<vector<vector<ll> > > >;
using vvvl = vector<vector<vector<ll> > >;
using vvl = vector<vector<ll> >;
using vl = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool> >;
using Graph = vector<vector<ll> >;
template<class T> using pq = priority_queue<T,vc<T>,less<T> >;
template<class T> using pq_g = priority_queue<T,vc<T>,greater<T> >;
ll dx[4] = {0,1,0,-1};ll ddx[8] = {1,1,0,-1,-1,-1,0,1};
ll dy[4] = {1,0,-1,0};ll ddy[8] = {0,1,1,1,0,-1,-1,-1};
bool out_grid(ll i, ll j, ll h, ll w){//trueならcontinueする
return(!(0 <= i && i < h && 0 <= j && j<w));
}
template<class T>
void cutoutV(vc<vc<T>> &G, ll H, ll W, ll mx, ll Mx, ll my, ll My){
if(!(0 <= mx && mx < H && 0 < Mx && Mx <= H && mx < Mx))return;
if(!(0 <= my && my < H && 0 < My && My <= H && my < My))return;
rep(i,Mx - mx)rep(j,My - my){
G[i][j] = G[i + mx][j + my];
}
G.resize(Mx - mx, vc<T>(My - my));
return;
}
ll modpow(ll x,ll y,ll m){
ll a = x;
a %= m;
ll cnt = 0;
ll ans = 1;
while(y > 0){
if((1ll << cnt) & y){
y ^= (1ll << cnt);
ans *= a;
ans %= m;
}
a = a*a;
a %= m;
cnt++;
}
return ans;
}
ll npow(ll x,ll y){
ll a = x;
ll cnt = 0;
ll ans = 1;
while(y > 0){
if((1ll << cnt) & y){
y ^= (1ll << cnt);
ans *= a;
}
a = a*a;
cnt++;
}
return ans;
}
struct Edge {
ll to;
ll cost;
};
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
// ai+bj=g
// ai+bj=gcd(a,b)なるi,jを求める
ll extgcd(ll a, ll b, ll& i, ll& j) {
if (b == 0) { i = 1; j = 0; return a;}
ll p = a/b, g = extgcd(b,a-b*p,j,i);
j -= p*i;
return g;
}
vl topological_sort(const vvl& G){
ll N = (ll)G.size();
vl indeg(N, 0), order;
queue<ll> que;
rep(u, N){
for(ll v : G[u]) indeg[v]++;
}
rep(i, N){
if(indeg[i] == 0) que.push(i);
}
while(!que.empty()){
ll u = que.front();
que.pop();
order.pb(u);
for(ll v : G[u]){
indeg[v]--;
if(indeg[v] == 0) que.push(v);
}
}
return order;
}
ll MOD = 998244353;
void print(ld x){printf("%.20Lf\n", x);}
//using mint = modint998244353;
////////////////////////////////////////////////////////////////
vl makediv(ll n) {
vl ld, ud;
for (ll i = 1; i * i <= n; i++) {
if (n % i == 0) {
ld.push_back(i);
if (n / i != i) {
ud.push_back(n / i);
}
}
}
reverse(ud.begin(), ud.end());
ld.insert(ld.end(), ud.begin(), ud.end());
return ld;
}
struct PrimeFact {
vl spf;
PrimeFact(ll N) { init(N); }
void init(ll N) { // 前処理。spf を求める
spf.assign(N + 1, 0);
for (ll i = 0; i <= N; i++) spf[i] = i;
for (ll i = 2; i * i <= N; i++) {
if (spf[i] == i) {
for (ll j = i * i; j <= N; j += i) {
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
}
map<ll, ll> get(ll n) { // nの素因数分解を求める
map<ll, ll> m;
while (n != 1) {
m[spf[n]]++;
n /= spf[n];
}
return m;
}
};
int main(){
ll N;
cin >> N;
vc<ld> dp(N+1,0);
vl memo(N+1,-1);
PrimeFact pf(N);
nfor(i,2,N+1){
vl res = makediv(i);
for(auto x : res){
ll cnt = x;
if(memo[x] != -1){
cnt = memo[x];
}else{
auto m = pf.get(x);
for(auto [idx,val] : m){
cnt /= idx;
cnt *= (idx - 1);
}
memo[x] = cnt;
}
dp[i] += dp[i / x] * ld(cnt) / ld(i);
}
dp[i]++;
dp[i] = dp[i] * ld(i) / ld(i-1);
}
print(dp[N]);
}