题目链接:Click here~~
题意:
求 s 的阶乘在 k 进制下阶乘的末尾 0 的个数。(s 以 k 进制形式给出)
解题思路:
先考虑关于任意一个数 x 在 k 进制下末尾 0 的个数等价于求什么。
首先,x 可以表示成 a[0] * k^0 + a[1] * k^1 + ... + a[m] * k^m 的形式。
如果 x 的末尾有 b 个 0,那么 a[0], a[1], ... , a[b-1] 都等于 0,即 x 又能表示成 a[b] * k^b + a[b+1] * k^(b+1) + ... + a[m] * k^m,
进一步地,提取公因式 k^b,表示成 y * k^b,且有 y % k = a[b] % k != 0。
所以,只要找到最大的 b,满足 x % k^b = 0,就是我们要的答案。
如果这题只是问 x 的话,直接暴力找就可以了,复杂度才 O(log(k,x))。
但是问的是 x 的阶乘,不妨把问题转化一下,把 x 和 k 全部表示成素数相乘的形式,
那么即使是对于阶乘,我们同样可以求得 x 的阶乘对于某个素因子 p 的指数。
最后,对于 k 的每个素因子 p,在 x 的表示中对指数取个 min 就是答案了。
#include <vector> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1e2 + 5; char str[N]; int digit(char c) { if(c >= '0' && c <= '9') return c - '0' + 0; else if(c >= 'A' && c <= 'Z') return c - 'A' + 10; else return 'Z' - 'A' + 11 + c - 'a'; } bool is_prime(int x) { if(x == 1) return false; for(int i=2;i*i<=x;i++) if(x % i == 0) return false; return true; } long long cnt(long long x,int p) { long long ret = 0; while(x >= p) { ret += x / p; x /= p; } return ret; } int main() { int k; while(~scanf("%s%d",str,&k)) { long long s = 0; int len = strlen(str); for(int i=0;i<len;i++) { s = s * k + digit(str[i]); } long long ans = (1ULL << 63) - 1; for(int i=2;i<=k;i++) { if(k % i != 0 || !is_prime(i)) continue; int d = 0; while(k % i == 0) { k /= i; d++; } ans = min(ans, cnt(s,i) / d); } printf("%lld\n",ans); } return 0; }