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