Codeforces Manthan Codefest 19 G問題 - Polygons

Source

Codeforces Manthan Codefest 19 G問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20190830-1）のコード

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

//no-unlocked
int N, K;
int ps, p[78498];
int phi[1000001];
{
  int i, j, k, d, mx, mxi;
  ll res = ll_inf, tmp;
  
  rd(N,K);

  if(K==1) wt(3), return 0;
  
  ps = Prime(N+1, p);
  d = (N-2) - K;

  rep(i,N+1) phi[i] = i;
  rep(k,ps) for(i=p[k];i<=N;i+=p[k]) phi[i] = (ll)phi[i] * (p[k]-1) / p[k];
  phi[1] = phi[2] = 0;

  tmp = 1;
  rep(i,N+1) tmp += phi[i];
  sort(phi,phi+N+1);
  rep(i,d) tmp -= phi[N-i];
  res <?= tmp;

  res++;
  wt(res);
}

Current time: 2024年04月27日02時58分54秒
Last modified: 2019年08月30日20時26分24秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る

Logged in as: unknown user (not login)