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; }