Codeforces Round #563 DIV2 E問題 - Ehab and the Expected GCD Problem

Source

Codeforces Round #563 DIV2 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20190608-2）のコード

C++に変換後のコードはこちら

//no-unlocked

int N;
mint fac[1000001];

int fs, f[20];

mint solve(int M){
  int i, j, k;
  int x, y;
  mint res, tmp;

  fs = FactorM(M, f);

  res = 0;
  do{
    tmp = 1;
    j = 1;
    x = 0;
    rep(i,fs){
      k = j * f[i];
      y = N - N / k - x;
      tmp *= fac[y+x] / fac[x] if[x, - fac[y+x-1] / fac[x-1]];
      j = k;
      x += y;
    }
    res += tmp;
  }while(next_permutation(f,f+fs));

  return res;
}

{
  int i, j;
  mint res;

  rd(N);
  fac[0] = 1;
  rep(i,1,N+1) fac[i] = fac[i-1] * i;

  j = 1;
  while(2j <= N) j *= 2;
  res = solve(j);
  if(j>=2 && j/2*3 <= N) res += solve(j/2*3);
  wt(res);
}

Current time: 2024年04月20日07時34分35秒
Last modified: 2019年06月08日14時22分54秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF563 CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)