a241 - 第二題：1 / x 是有限小數

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在 1 到 n 之間，有多少個正整數 x 使得 1/x 是有限小數。

解題思路

一個分數 1/x 是有限小數，當且僅當 x 的質因數分解中，除了 2 和 5 以外，沒有其他的質因數。換句話說，x 必須是 2^i * 5^j 的形式，其中 i 和 j 都是非負整數。

程式碼預先計算了 2 的 0 到 26 次方，以及 5 的 0 到 12 次方，然後對於每個輸入 n，遍歷所有可能的 i 和 j，計算 2^i * 5^j 的值，如果這個值小於等於 n，則將答案加 1。

複雜度分析

• 時間複雜度: O(n * log(n))。外層迴圈遍歷測試案例數量，內層迴圈的嵌套迴圈實際上是在遍歷所有可能的 2^i * 5^j 的值，直到大於 n。由於 2^i 和 5^j 的增長速度很快，因此內層迴圈的次數大致與 log(n) 成正比。
• 空間複雜度: O(1)。程式碼使用固定大小的陣列 two 和 five，其大小不依賴於輸入 n。

程式碼

#include <stdio.h>
long long int two[27]={1},five[13]={1};
int main(){
	for(int i=1;i<27;++i)
		two[i]=two[i-1]<<1;
	for(int i=1;i<13;++i)
		five[i]=five[i-1]*5;
	long long int n;
	int t;
	scanf("%d",&t);
	while(t--){
		int ans=-1;
		scanf("%lld",&n);
		for(int i=0;i<27;++i)
			for(int j=0;j<13;++j)
				if(two[i]*five[j]<=n){
					++ans;
				}
		printf("%d\n",ans);
	}
}