首页 > itarticle > uva 11802 – all your bases belong to us

uva 11802 – all your bases belong to us

admin 11月 11, 2020 0

contents

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: %lldn", ++cases, ((ret1 - ret2)%mod + mod)%mod);
	}
	return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能