結果

問題 No.2829 GCD Divination
ユーザー tnakao0123tnakao0123
提出日時 2024-08-05 18:49:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,674 bytes
コンパイル時間 1,167 ms
コンパイル使用メモリ 68,368 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-08-05 18:49:41
合計ジャッジ時間 3,142 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 2 ms
6,940 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2829.cc:  No.2829 GCD Divination - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 10000000;
const int MAX_P = 3200;

/* typedef */

using vi = vector<int>;
using vb = vector<bool>;
using vd = vector<double>;

/* global variables */

vb primes;
vi pnums;

/* subroutines */

int gen_primes(int maxp) {
  primes.assign(maxp + 1, true);
  primes[0] = primes[1] = false;

  int p;
  for (p = 2; p * p <= maxp; p++)
    if (primes[p]) {
      pnums.push_back(p);
      for (int q = p * p; q <= maxp; q += p) primes[q] = false;
    }
  for (; p <= maxp; p++)
    if (primes[p]) pnums.push_back(p);
  return (int)pnums.size();
}

bool prime_decomp(int n, vi &ps, vi &ds) {
  ps.clear(), ds.clear();

  for (auto pi: pnums) {
    if (pi * pi > n) {
      if (n > 1) ps.push_back(n), ds.push_back(1);
      return true;
    }

    if (n % pi == 0) {
      int fi = 0;
      while (n % pi == 0) n /= pi, fi++;
      ps.push_back(pi), ds.push_back(fi);
    }
  }
  return false;
}

void decomp_ps(int n, vi &ps, vi &ds) {
  ds.clear();
  for (auto p: ps) {
    int fi = 0;
    while (n % p == 0) fi++, n /= p;
    ds.push_back(fi);
  }
}

int calc(vi &ds0, vi &ds1, vi &nds) {
  int p = 1, k = ds0.size();
  for (int i = 0; i < k; i++)
    if (ds0[i] == ds1[i]) p *= nds[i] - ds1[i] + 1;
  return p;
}

void printv(vi &v) {
  for (auto a: v) printf(" %d", a); putchar('\n');
}

/* main */

int main() {
  gen_primes(MAX_P);

  int n;
  scanf("%d", &n);

  vi ps, nds;
  prime_decomp(n, ps, nds);
  int k = ps.size();
  //printf("ps="), printv(ps), printf("nds="), printv(nds);

  vi as;
  for (int p = 1; p * p <= n; p++)
    if (n % p == 0) {
      as.push_back(p);
      int q = n / p;
      if (q != p) as.push_back(q);
    }
  sort(as.begin(), as.end());
  int m = as.size();
  //printf("as="), printv(as);

  vector<vi> ads(m);
  for (int i = 0; i < m; i++) decomp_ps(as[i], ps, ads[i]);
  
  vd es(m, 0.0);
  vi ss(m);
  for (int i = 1; i < m; i++) {
    int sum = 0;
    for (int j = 1; j <= i; j++)
      sum += (ss[j] = calc(ads[j], ads[i], nds));
    ss[0] = n - sum;
    //printf("n=%d, sum=%d\nss=", n, sum);
    //for (int j = 0; j <= i; j++) printf(" %d", ss[j]); putchar('\n');

    // e[n] = 1 + e[0]*ss[0]/n+e[1]*ss[1]/n+...+e[n]*ss[n]/n
    // -> e[n](n-ss[n]) = n + e[0]*ss[0]+e[1]*ss[1]+..+e[n-1]*ss[n-1]
    double esum = 0.0;
    for (int j = 0; j < i; j++) esum += es[j] * ss[j];
    es[i] = (n + esum) / (n - ss[i]);
  }

  printf("%.10lf\n", es[m - 1]);
  
  //for (int i = 0; i < m; i++)
  //  printf(" es[%d] = %lf\n", as[i], es[i]);
  return 0;
}
0