解題區/解題區 - UVa

UVa 11802 - All Your Bases Belong to Us

contents

  1. 1. Input
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

It is very easy to find number of trailing zero in n! for a particular base b. In this problem you have to do the reverse. You have to find for how many bases b, n! has k trailing zeros in base b.

Input

Input starts with a positive number T≤10000, denoting the number of test cases to follow.

Each test case contains two non-negative integers, n≤1015 and 1≤k≤1015 in a line. You may assume and n/k<500.
Output

For each input output one line containing the number of different bases. Print the solution modulo 1000000007

Sample Input

1
2
3
4
5
6
5
10 2
10 3
10 4
10 5
10 8

Sample Output

1
2
3
4
5
Case 1: 24
Case 2: 0
Case 3: 4
Case 4: 0
Case 5: 1

Solution

題目描述：

對於 n! 的 b 進制數中，尾數恰好為 k 個 0 情況為何？

題目解法：

質因數分解，找到每一個質數的次方數，根據數學組合和排容原理得到，大於等於 k 個 0 的基底情況個數為何，因此

對於 2^n1 * 3^n2 * 5^n3 * 7^n4 ... = n!，

base = pi^mi * ...，保證 (pi^mi)^k => mi * k <= ni。計算 mi (0, 1, …, ni/k)的可能情況總數乘積即可。

最後用排容原理吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
#include <stdio.h>
#include <stdlib.h>
#define LL long long
#define maxL (10000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
int P[5050], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000;
    for(i = 2; i < n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int main() {
    sieve();
    const long long mod = 1000000007LL;
    int testcase, cases = 0;
    long long N, K;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lld %lld", &N, &K);
        long long ret1 = 1, ret2 = 1;
        for(int i = 0; i < Pt; i++) {
            long long p = P[i], cnt = 0;
            while(p <= N)
                cnt += N / p, p *= P[i];
            if(cnt < K)
                break;
            ret1 *= cnt/K + 1;
            ret2 *= cnt/(K+1) + 1;
            ret1 %= mod;
            ret2 %= mod;
        }
        printf("Case %d: %lld\n", ++cases, ((ret1 - ret2)%mod + mod)%mod);
    }
    return 0;
}