[UVA] 12090 - Counting Zeroes
F |
Counting Zeroes Input: Standard Input Output: Standard Output |
In our daily life we often meet some stupid persons. They tend to do things by hand which can only be done with computers. Our friend Hashmat is such a person and now he is counting with abacus, pencil and paper the summation of trailing zeroes of a particular number in all possible number systems (Of course, I am talking about the common number system like decimal, binary, hexadecimal or n-based number system).
We the average intelligent peoples know what a number system is. Our daily life number system is the decimal (10-based) number system, our corporate life number system is the binary (2-based) number system. A number may or may not have trailing zeroes in certain number system. For example in decimal number system 102010 (It means 1020 is a number whose base is 10) has 1 trailing zero but in hexadecimal number system 102010 has no trailing zeroes. Let us create a function fzero(n,b), which actually denotes the number of trailing zeroes of n in b-based number system. So fzero(102010,10)=1 and fzero(102010,16)=0. Although for a certain number and certain base the task is trivial but it is very time consuming to do it for all possible number systems with the help of only pencil and paper. So your job is now to help Hashmat, so that he can complete this task and do something meaningful in life. In other words given the value of n your job is to find out the value of:
Input
The input file contains at most 400 lines of inputs. Each line contains a decimal integer n (0<n<=1013).
Input is terminated by a line containing a single zero.
Output
For each line of input produce one line of
output. This line contains the input number followed by the value of .
Sample Input Output for Sample Input
10 20 0 |
10 3 20 6
|
Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman
如果要在某個基底b下, 尾數要存在有 0, 則這個基底必然是 n 個因數。
因此快速生成 n 的所有因數，而由於還是不知道在那個基底下有多少個 0，因此還是需要手動算一下。
數學不好 orz
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define maxL (10000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
long long p[700000], pt = 0;
void sieve() {
register int i, j, k;
SET(1);
int n = 10000000;
for(i = 2; i <= n; i++) {
if(!GET(i)) {
p[pt++] = i;
for(k = n/i, j = i*k; k >= i; k--, j -= i)
SET(j);
}
}
//printf("%d\n", pt);
}
vector<pair<long long, int> > pfactor;
vector<long long> factor;
void dfs(int idx, long long n) {
if(idx == pfactor.size()) {
factor.push_back(n);
return;
}
int i;
long long p = (long long)pfactor[idx].first, t = 1;
for(i = pfactor[idx].second; i >= 0; i--) {
dfs(idx+1, n*t);
t = t*p;
}
}
int main() {
/*freopen("in.txt", "r+t", stdin);
freopen("out2.txt", "w+t", stdout);*/
sieve();
long long n, on;
int i, j, k;
while(scanf("%lld", &n) == 1 && n) {
if(n < 0) {while(1);}
pfactor.clear();
factor.clear();
on = n;
for(i = 0; i < pt && p[i]*p[i] <= n; i++) {
if(n%p[i] == 0) {
int e = 0;
while(n%p[i] == 0)
e++, n /= p[i];
pfactor.push_back(make_pair(p[i], e));
}
}
if(n != 1)
pfactor.push_back(make_pair(n, 1));
dfs(0, 1);
int ret = 0;
for(i = 0; i < factor.size(); i++) {
if(factor[i] == 1) continue;
n = on;
while(n%factor[i] == 0)
n /= factor[i], ret++;
}
printf("%lld %d\n", on, ret);
}
return 0;
}
/*
10000000000000
9999999999999
9999999900000
*/