ZOJ Monthly, June 2012 K : Factorial Problem in Base K
問題概要
s!をK進数で書いたとき末尾に0がいくつあるか求める問題。s<2^62, K<62。
解法
Kを素因数分解してその素因数がs!にいくつ含まれるか求める。例えばK=8のときなんかは2でs!がいくつ割りきれるか求め、それを3で割ったものが0の個数になる。K=24とかだったらそれと3でs!がいくつ割りきれるかのminをとったものが答。
acceptされたコード
上限は十分大きく取っておく必要がある。
#include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <iostream> using namespace std; typedef long long int64; char buf[1000]; int64 S; int K; bool init() { return scanf(" %s %d", buf, &K) != EOF; } int toi(char ch) { if('0' <= ch && ch <= '9') return ch&15; if('A' <= ch && ch <= 'Z') return ch - 'A' + 10; return ch - 'a' + 36; } int64 solve() { const int L = strlen(buf); S = 0; for (int i = 0; i < L; ++i) { S = K * S + toi(buf[i]); } map<int,int> dict; int M = K; for (int i = 2; i < 70; ++i) { for (;M % i == 0;) { ++dict[i]; M /= i; } } unsigned long long ans = ~0LL; for (map<int,int>::iterator itr = dict.begin(); itr != dict.end(); ++itr) { unsigned long long cnt = 0; int64 T = S / itr->first; for (;T; T /= itr->first) { cnt += T; } ans = min( ans, cnt / (unsigned long long)itr->second ); } return (int64)ans; } int main() { for (;init();) { printf("%lld\n", solve()); } return 0; }