Koios1143的筆記

UVa 10061

發表於 分類於

UVa 10061

題目

http://domen111.github.io/UVa-Easy-Viewer/?10061

給兩個數 $n$, $m$ ，求

  1. $n!$ 在 $m$ 進位制下尾數有多少個 $0$
  2. $n!$ 在 $m$ 進位制下是幾位數

想法

  1. 幾位數

問幾位數的問題比較簡單，如同前一題，只是進位制不同

要計算 在 $m$ 進位制下是幾位數，等同於計算 $log_{m}{n}+1$ 取整數

由於內建的函式庫並沒有直接計算 $log$ 底數為任意數的方式，這裡要使用換底公式

$$log_{a}{b} = \frac{log_{n}{b}}{log_{n}{a}}
$$

根據 $logab = loga + logb$ 的性質，可以得到

$$\sum_{i=1}^{n}{log_{m}{i}}
$$

兩個性質合起來

$$\sum_{i=1}^{n}{\frac{log_{10}{i}}{log_{10}{m}}}
$$

  1. 尾數有多少個

先從 10 進位開始想，尾數要是 0 則它必定會是 10 的整數倍

例如: 10, 100, 1000, 1020 …

這個數一定要有 10 的因數 ，也就是他必須要至少同時有一個 2 和 5 的質因數

換到其他進位制仍然相同

所以說，我們只需要紀錄 $n!, m$ 的質因數各有多少個

如果說 $m$ 的質因數有 $P={p_1, p_2, p_3}$

那麼 $n!$ 至少要包含整數倍的 $P$ ，才能是 $m$ 的整數倍

所以接下來針對 $m$ 的每個質因數 $i$ ，計算 $i$ 在 $n!$ 中的個數與在 $m$ 中的個數之比值，其中最小值就會是答案

例如: $n=7,\ m=16$
整理一下 $n!$ 的質因數個數

tbl 2 3 4 5 6 7
個數 4 2 0 1 0 1

整理一下 $m$ 的質因數個數

mPrime 2 3 4 5 6 7
個數 4 0 0 0 0 0

所以說，必須至少含有 4 個 2 ，尾數才能有一個 0
這裡可以發現答案是 $tbl[2]/mPrime[2] = 1$

  1. 質因數個數

至於質因數個數的部分，我們可以先預先建立一個表格，紀錄每個數字內的最小質數

例如: 10 -> 2 ; 7 -> 7 ; 9 -> 3

接下來，我們每次除以最小質因數，經過的就會是他的質因數了

例如: 36 –(/2)–> 18 –(/2)–> 9 –(/3)–> 3 –(/3)–> 1

求得 $36 = 2^2\times3^2$

  1. 數字內最小質因數

他就會像是這樣，將每個是自己倍數的數值紀錄成自己

例如: 偶數都會被記錄成 2 , 質數都會記錄成自己

Code

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
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
const int MaxN = 1048577;
int n,m,prime[MaxN],tbl[MaxN],mPrime[MaxN];
void init(){
	for(int i=1 ; i<MaxN ; i++){
		tbl[i]=0;
		mPrime[i]=0;
	}
	int tmp=m;
	while(tmp>1){
		mPrime[prime[tmp]]++;
		tmp/=prime[tmp];
	}
}
void update_tbl(int x){
	while(x>1){
		tbl[prime[x]]++;
		x/=prime[x];
	}
}
void update_prime(){
	prime[1]=1;
	for(int i=2 ; i<=MaxN ; i++){
		if(prime[i]) continue;
		for(int j=i ; j<=MaxN ; j+=i){
			if(!prime[j])
				prime[j]=i;
		}
	}
}
int main(){
	update_prime();
	while(cin>>n>>m){
		init();
		for(int i=2 ; i<=n ; i++){
			update_tbl(i);
		}
		int ans1=2147483647;
		for(int i=2 ; i<=m ; i++){
			if(mPrime[i]){
				ans1=min(ans1, tbl[i]/mPrime[i]);
			}
		}
		double ans2=0;
		for(int i=1 ; i<=n ; i++){
			ans2+=log(i)/log(m);
		}
		ans2=(int)(ans2)+1;
		cout<<fixed<<setprecision(0)<<ans1<<' '<<ans2<<"\n";
	}
	return 0;
}

時間複雜度

預處理質數時間複雜度約為 $O(NlogN)$

每次初始化的時間複雜度約為 $O(N+logm)$

計算尾數的時間複雜度約為 $O(m)$

計算位數的時間複雜度約為 $O(n)$

總時間複雜度約為 $O(NlogN+(測資數量)\times(N+logm+m+n))$

大約為 $O(NlogN+(測資數量)\times(N))$