g470 - 12869: Zeroes

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在給定範圍 [low, high] 內，fzero(v) 的不同值的數量，其中 fzero(v) 表示 v! 尾隨零的數量。

解題思路

計算尾隨零的數量等同於計算 v! 中因子 5 的數量。因為因子 2 的數量總是比因子 5 多，所以只需要計算因子 5 的數量即可。 對於給定的範圍 [low, high]，我們需要計算不同尾隨零數量的數量。 由於 fzero(v) 是一個非遞減函數，我們可以計算 fzero(low) 和 fzero(high)，然後計算從 fzero(low) 到 fzero(high) 的不同值的數量。 為了避免直接計算階乘，我們可以使用以下公式計算 fzero(v)： fzero(v) = v/5 + v/25 + v/125 + ... 程式碼中，x 和 y 分別代表 low 和 high。 x+=5-x%5; 和 y+=5-y%5; 的作用是將 x 和 y 分別調整到下一個 5 的倍數，以便計算 fzero(x) 和 fzero(y)。 (y-x)/5+1 計算了從 x 到 y (包含 x 和 y) 的 5 的倍數的數量，這也代表了 fzero(v) 的不同值的數量。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
long long x,y;
int main(){
	cin.tie(0);cout.tie(0) ;ios::sync_with_stdio(false);
	while(cin >> x >> y){
		if(x==0&&y==0)break;
		x+=5-x%5;
		y+=5-y%5;
		cout << (y-x)/5+1 << "\n"; 
	}
}