trailing-zeros

Trailing Zeros

CSES easy

أوجد عدد الأصفار في نهاية \(n!\) (عدد الأصفار في آخر كتابته العشرية). مثلًا، \(20! = 2432902008176640000\) وفي نهايته \(4\) أصفار.

القيود:

\(1 \le n \le 10^9\)

الإدخال:

سطر واحد: عدد صحيح \(n\).

المخرجات:

عدد صحيح واحد — عدد الأصفار في نهاية \(n!\).

مثال:

الإدخال:

المخرجات:

الحل

العدد \(n!\) كبير جدًا فلا يمكن حسابه، لذلك نعدّ أصفاره بطريقة أخرى.

كل صفر في النهاية يأتي من عامل \(10 = 2 \cdot 5\). في حاصل الضرب \(1 \cdot 2 \cdot \ldots \cdot n\) عوامل \(2\) أكثر بكثير من عوامل \(5\)، لذلك عدد الأصفار في النهاية يساوي عدد عوامل \(5\) في \(n!\).

نعدّ عوامل \(5\):

\(\lfloor n / 5 \rfloor\) عددًا من \(1\) إلى \(n\) تقبل القسمة على \(5\)، وكل منها يعطي عامل \(5\) واحدًا؛
\(\lfloor n / 25 \rfloor\) منها تقبل القسمة على \(25\)، وكل منها يعطي عامل \(5\) إضافيًا؛
\(\lfloor n / 125 \rfloor\) منها تعطي عامل \(5\) ثالثًا، وهكذا.

إذن الجواب هو \(\lfloor n / 5 \rfloor + \lfloor n / 25 \rfloor + \lfloor n / 125 \rfloor + \ldots\)، ونتوقف عندما تصبح قوة \(5\) أكبر من \(n\).

عندما \(n = 20\): \(\lfloor 20 / 5 \rfloor = 4\) و \(\lfloor 20 / 25 \rfloor = 0\)، إذن الجواب \(4\).

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;

    long long zeros = 0;
    // n / 5 numbers are divisible by 5, n / 25 by 25, and so on
    for (long long power = 5; power <= n; power *= 5) {
        zeros += n / power;
    }

    cout << zeros << "\n";
}