2013-08-11 21:31:42| 人氣2,072| 回應0 | 上一篇 | 下一篇

[UVA] 12090 - Counting Zeroes

推薦 0 收藏 0 轉貼0 訂閱站台

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 1020₁₀ (It means 1020 is a number whose base is 10) has 1 trailing zero but in hexadecimal number system 1020₁₀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(1020₁₀,10)=1 and fzero(1020₁₀,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<=10¹³).

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 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
*/

我要檢舉

#12090#Counting Zeroes

台長： Morris

您可能對以下文章有興趣

[UVA][矩形聯集] 870 - Intersecting Rectangles

[UVA][Easy] 12611 - Beautiful Flag

[UVA][DP] 11151 - Longest Palindrome

[UVA] 10050 - Hartals

人氣(2,072) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][插頭DP] 11270 - Tiling Dominoes
此分類上一篇:[UVA][高斯消去] 12143 - Stopping Doom's Day

回應(0)