2

自然数の階乗の終わりに0を計算するという標準的な問題を解決しようとしています。私のコードは正常に動作しますが、オンライン ジャッジで「Time Limit Exceeded」エラーが発生します。コードを最適化する方法についてここで質問することにしました。

#include <iostream>

using namespace std;


int count (int n)
{
    int result = 0;
    for (unsigned int i = 5; i <= n; i += 5)
    {
        int temp = i;
        while (!(temp % 5))
        {
            ++result;
            temp /= 5;
        }
    }
    return result;
}



int main()
{
    int N;
    cin >> N;
    cin.get();
    for (unsigned int i = 0; i < N; ++i)
    {
        int n;
        cin >> n;
        cin.get();
        cout << count (n) << endl;
    }
    return 0;
}

前もって感謝します。

4

2 に答える 2

2

これを試して：

int count (int n)
{
    int result = 0;
    for (unsigned int i = 5; i <= n; i *= 5)
        result += n / i;
    return result;
}

1*2*..*Nには、N/5で割り切れる因数があり5ます。それらのうち、 、 ... でN/25割り切れる25

于 2013-04-02T12:13:44.327 に答える
1

5 で割り切れるすべての数をチェックする必要はありません。代わりに、単純な級数で 5 を数えることができます。

count =  n div 5 + n div 25 + n div 125...
于 2013-04-02T12:19:46.317 に答える