UVa 10061 - How many zero's and how many digits ?

#数学 #分解质因数
Published on 2016-03-02

题目地址

描述

给定 n(n<221),B(1<B≤800)n(n<2^{21}), B(1< B\le 800)，求 n!n! 在 B 进制下面的位数以及后缀 0 的个数。

样例输入

2 10
5 16
5 10

样例输出

0 1
0 2
1 3

分析

这么简单的题都看题解，看来我数论是完蛋了QAQ。。。。。。
先求位数，假如我们设 n!n! 在 B 进制下是 mm 位的，那么就有：

Bm−1≤n!<BmB^{m - 1}\le n!<B^m

显然无法算，又因为 y=logxy = \log x，在 (0,+∞)(0, +\infty) 内单调递增，所以不等式可取对数，以 BB 为底数：

m−1≤∑1≤k≤nlogbk<mm - 1\le \sum\limits_{1\le k\le n}\log_bk < m

所以答案就是 ⌊∑1≤k≤nlogbk⌋+1\left\lfloor\sum\limits_{1\le k\le n}\log_bk\right\rfloor + 1
再求后缀零的个数，回忆十进制，后缀 0 的个数取决于 n!n! 中有多少个 10，换句话说就是 [1,n][1, n] 全体分解质因数，一共能组成多少个 10，显然 10=2×510 = 2 \times 5，2 和 5 的数量中较小的那个就是 n!n! 中 10 的个数。
一般的，如果 [1,n][1, n] 分解质因数之后得到 SS，B 的分解为 B=p1k1p2k2...pmkmB = p_1^{k_1}p_2^{k_2}...p_m^{k_m}，那么后缀 0 的个数就是 min⌊S[px]kx⌋\min{\left\lfloor\frac{S[p_x]}{ k_x}\right\rfloor}

代码

//  Created by Sengxian on 3/2/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 10061 分解质因数, 对数
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int maxb = 800 + 3, INF = 0x3f3f3f3f;
vector<int> primes;
bool isPrime[maxb];
int n, b;

ll digit() {
    double sum = 0, logb = log(b);
    for(int i = 1; i <= n; ++i)
        sum += log(i) / logb;
    return (ll)floor(sum) + 1;
}

inline int getCnt(ll x) {
    int cnt = 0, _x = x;
    while(x <= n) {
        cnt += n / x;
        x *= _x;
    }
    return cnt;
}

int trailingzero() {
    int ans = INF;
    for(int i = 0; i < primes.size() && primes[i] <= b; ++i)
        if(b % primes[i] == 0) {
            int _b = b, cnt = 0;
            while(_b % primes[i] == 0) _b /= primes[i], cnt++;
            ans = min(ans, getCnt(primes[i]) / cnt);
        }
    return ans;
}

int main() {
    fill(isPrime, isPrime + maxb, true);
    for(int i = 2; i < maxb; ++i) {
        if(isPrime[i]) primes.push_back(i);
        for(int j = 0; j < primes.size() && primes[j] * i < maxb; ++j) {
            isPrime[primes[j] * i] = false;
            if(i % primes[j] == 0) break;
        }
    }
    while(scanf("%d%d", &n, &b) == 2)
        printf("%d %lld\n", trailingzero(), digit());
    return 0;
}

附加输入

0 2
1 2
2 9 
100 23 
23 101 
23233 344 
34 799 
1000000 799
1000010 800
1048575 2
1048575 3
1048575 17
1048575 101
1048575 799
1048575 800

附加输出

0 1
0 1
0 1
4 117
0 12
552 36014
0 14
21737 1917527
125000 1917188
1048555 19458736
524281 12277096
65533 4760591
10484 2922517
22794 2018112
131070 2017734
UVa 10090 - Marbles