Codeforces Round #256 DIV2 E問題 - Divisors

Source

Codeforces Round #256 DIV2 E問題
Problem description

問題概要

$a = [a_0,a_1,\ldots,a_{k-1}]$ を整数からなるリストとして,$f(a)$ は整数からなるリストで,$a_0$ の約数を小さい方から並べて,$a_1$ の約数を小さい方から並べて,…,$a_{k-1}$ の約数を小さい方から並べたもの.(例は問題原文を参照)
整数 $X$ に対して,
$\quad X_0 = [X],$
$\quad X_{i+1} = f(X_i)$
でリストからなる列を定める.
$X_K$ を求める問題.ただし,リストの要素の数が $10^5$ より大きければ,最初の $10^5$ 個のみを求める.

解法

深さ優先探索をしながら全列挙する.
$X$ の約数を列挙し,$X$ の約数をそれぞれノードとみなして,どこの約数からどこの約数が生成されるかというグラフを作る.
枝を辿るときは,小さい約数から順番に辿るとして,$X$ から移動した回数が $K$ のものを列挙していけば良い.
ただし,$L=10^5$ として,$L$ 個列挙できたらそこで終了する.
後は,間に合わない場合のケースを個別に考えて,それをケアすれば良い.
まず,$X=1$ または $K=0$ の場合は,いつまでたっても要素数が増えず答えは $[X]$.
そうでなくて,$K$ が $L$ より大きい場合は,先頭の $1$ が増え続けるので,$1$ を $L$ 個出力して終わり.
深さ優先探索で,訪れているノードが,$1$ に対応するノードなら,それから $1$ にしか枝が張られないので,辿るのを即座にやめて $1$ を出力して戻る.
また,深さ優先探索で,訪れているノードが,素数に対応するノードなら,残された移動回数だけ $1$ が増えるので,$1$ を移動回数分だけ出力して,素数を出力して戻ることもできる.
おそらく,出力する数の最大値を $L = 10^5$ として,時間計算量は $O(L \log L)$ 程度.

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(ll x, char c){int i,sz=0,m=0;char buf[20];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

#define LIM 100000

ll X, K;

ll yaku[10000];
int yakus;
vector<int> edge[10000];
int rest;

void dfs(int depth, int node){
  int i;

  if(rest==0) return;

  if(node==0){
    rest--;
    writer(yaku[node], ' ');
    return;
  }

  if(node==1){
    rep(i,K-depth){
      rest--;
      writer(yaku[0], ' ');
      if(rest==0) return;
    }
    rest--;
    writer(yaku[node], ' ');
    return;
  }

  if(depth==K){
    rest--;
    writer(yaku[node], ' ');
    return;
  }

  rep(i,edge[node].size()){
    dfs(depth+1, edge[node][i]);
    if(rest==0) return;
  }
}

void solve(){
  ll i, j, k;
  
  rest = LIM;
  if(X==1 || K==0){
    writer(X, ' ');
    return;
  }

  if(K>=LIM){
    rep(i,LIM) writer(1LL, ' ');
    return;
  }

  yakus = 0;
  for(i=1;i*i<=X;i++) if(X%i==0){
    yaku[yakus++] = i;
    if(X/i!=i) yaku[yakus++] = X/i;
  }
  sort(yaku, yaku+yakus);

  rep(i,yakus) edge[i].clear();
  rep(i,yakus) rep(j,i+1) if(yaku[i]%yaku[j]==0) edge[i].push_back(j);

  dfs(0, yakus-1);
}

int main(){
  reader(&X);
  reader(&K);
  solve();

  myed;
  return 0;
}

Current time: 2017年07月23日17時41分04秒
Last modified: 2014年11月18日13時12分55秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF256 CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン: