土下座しながら探索中

主に競技プログラミング

LiveArchive 6396 : Factors

問題リンク : https://icpcarchive.ecs.baylor.edu/external/63/6396.pdf

問題概要 :
関数 f は2^63未満の正の整数 k を引数にとり、
k の素因数の異なるarrangementの数 n を返す関数である
例えば、 f(10) = 2 である
なぜなら、 10 = 2 * 5 = 5 * 2 であるから
また、 f(20) = 3 である
なぜなら、 20 = 2 * 2 * 5 = 2 * 5 * 2 = 5 * 2 * 2 であるから

2^63未満の正の整数 n が与えられるので、 f(k) = n となるような最小の k を求めよ
入力で与えられる n は k が 2^63未満となるものに限られる

解法 :
解説読みました..
http://www.csc.kth.se/~austrin/icpc/finals2013solutions.pdf

k = p1^e1 * p2^e2 * ... * pt^et とすると、 n = ( e1 + e2 + ... + et )! / ( e1! * e2! * ... * et! )
見ての通り、 n はp1, p2, ..., pt の値に影響しない
ならば、kを最小化したいなら p1, p2, ..., pt は小さい素数から順に割り当ててしまうのが良い
( p1 = 2, p2 = 3, ... )
また、 e1 >= e2 >= ... >= et としてもよい
ei < ej ( i >= j ) であるようなものがあっても良いのだが、
ei ejの順序はnに影響しないので、そのような場合はeiとejをスワップしてしまったほうが k を小さくできる
まとめると、
k = p1^e1 * p2^e2 * ... * pt^et ( p1 = 2, p2 = 3, ... かつ e1 >= e2 >= ... かつ k < 2^63 )
さて、このk、ここまで制約を厳しくすると、意外とそこまで多くないような気がする
使う素数は高々15個くらいまで ( それ以上だと、eiを全て1にしても2^63以上になる
また、e1から順番に全探索で決め打ちしていくとしても、eiの値は前よりも減少していくわけだし、kが2^63以上ならそこで終わりなので、
ちょっと全探索を書いて終わりそうか見てみると爆速なので、メモ化して投げるとAC
( e1は高々63で、e2は高々その半分もなくて、e3はe2のその半分もなくて、...と考えていくと、かなり大雑把に見積もっても2 * 10^6以下になるので、全探索で大丈夫そう )
(ちなみに解説によると、 上記の制約を満たすkは43606しかないらしい)


ちなみに、long longや__int128を使っても、素直に ( e1 + e2 + ... + et )! / ( e1! * e2! * ... * et! )を計算するとオーバーフローする
多倍長を書くか、JavaのBigIntegerを使うか、割り算をいい感じにするかしないとダメ

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()

using namespace std;

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}

const int m = 16;
__int128 maxi;
__int128 prim[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

map<__int128,__int128> rf;
__int128 calc_k(deque<int> &inp) {
  deque<int> deq;
  rep(i,(int)inp.size()) REP(j,2,inp[i]+1) deq.push_back(j);
  int limit = 0;
  rep(i,(int)inp.size()) limit += inp[i];
  sort(ALL(deq));
  __int128 k = 1;
  int i = 2;
  while( i <= limit ) {
    k *= (__int128)i;
    while( !deq.empty() && ( k % deq.front() == 0 ) ) {
      k /= deq.front();
      deq.pop_front();
    }
    while( !deq.empty() && ( k % deq.back() == 0 ) ) {
      k /= deq.back();
      deq.pop_back();
    }
    ++i;
  }
  while( !deq.empty() && ( k % deq.front() == 0 ) ) {
    k /= deq.front();
    deq.pop_front();
  }
  assert(deq.empty());
  return k;
}

void dfs(int cur, __int128 v,int limit,deque<int> &deq) {
  if( cur >= m ) return;
  __int128 w = v;
  rep(i,(limit+1)) {
    w = w * prim[cur];
    if( w >= maxi ) break;
    deq.push_back(i+1);
    __int128 k = calc_k(deq);
    assert( k );
    if( !rf.count(k) ) rf[k] = w;
    else rf[k] = min(rf[k],w);
    dfs(cur+1,w,i+1,deq);
    deq.pop_back();
  }
}

__int128 parse(string s) {
  __int128 n = 0;
  rep(i,(int)s.size()) {
    n *= (__int128)10;
    n += (__int128)( s[i] - '0' );
  }
  return n;
}

int main() {
  maxi = 1;
  REP(i,1,64) maxi = maxi * (__int128)2;
  deque<int> deq;
  dfs(0,1,63,deq);
  string s;
  while( cin >> s ) {
    __int128 n = parse(s);
    cout << n << " " << rf[n] << endl;
  }
  return 0;
}