How many zero's and how many digits ? UVA - 10061
Given a decimal integer number you will have to find out how many trailing zeros will be there in its
factorial in a given number system and also you will have to find how many digits will its factorial have
in a given number system? You can assume that for a b based number system there are b different
symbols to denote values ranging from 0 . . . b − 1.
Input
There will be several lines of input. Each line makes a block. Each line will contain a decimal number
N (a 20bit unsigned number) and a decimal number B (1 < B ≤ 800), which is the base of the number
system you have to consider. As for example 5! = 120 (in decimal) but it is 78 in hexadecimal number
system. So in Hexadecimal 5! has no trailing zeros.
Output
For each line of input output in a single line how many trailing zeros will the factorial of that number
have in the given number system and also how many digits will the factorial of that number have in
that given number system. Separate these two numbers with a single space. You can be sure that the
number of trailing zeros or the number of digits will not be greater than 231 − 1.
Sample Input
2 10
5 16
5 10
Sample Output
0 1
0 2
1 3
求k进制下，n的阶乘的位数以及末尾0数。
位数求法很简单：我们只要知道一个m位的b进制数n，n一定会满足 b^(m-1)<=n<b^m （用十进制数模拟一下，就可以得到结论），两边同时 取log(b) 得到 log(n) <= m，对于n！就是 log1+log2+...+log(n)。
然后求末尾0数的话，我们只要将其分解质因子，看能凑齐多少个k。具体看代码吧~
// Asimple #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <queue> #include <vector> #include <string> #include <cstring> #include <stack> #include <set> #include <map> #include <cmath> #define INF 0x3f3f3f3f #define mod 1000000007 #define debug(a) cout<<#a<<" = "<<a<<endl #define test() cout<<"============"<<endl using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 800+5; int n, m, T, len, cnt, num, ans, Max, k; //分解质因数 int count_zero(int n, int k) { int ans = INF; int p[maxn], q[maxn], c[maxn]; memset(c, 0, sizeof(c)); memset(q, 0, sizeof(q)); len = 0; for(int i=2; i<=k && k>1; i++) { if( k%i==0 ) p[len++] = i; while( k%i==0 ) { c[len-1]++; k /= i; } } for(int i=2; i<=n; i++) { int t = i; for(int j=0; j<len; j++) { while( t%p[j]==0 && t ) { q[j] ++; t /= p[j]; } } } for(int i=0; i<len; i++) { ans = min(ans, q[i]/c[i]); } return ans; } int digits(int n, int k) { double ans = 0.0; for(int i=1; i<=n; i++) { ans = ans + log10(i+0.0); } ans = ans/log10(k+0.0)+1.0; return (int)ans; } void input(){ while( cin >> n >> k ) { cout << count_zero(n, k) << " " << digits(n, k) << endl; } } int main() { input(); return 0; }
