Câte zerouri are n factorial la final? C++

Factorialul lui n, notat n!, este produsul numerelor de la 1 la n. Prin convenție, 0!=1. Pentru 10, produsul este 3628800 și are două zerouri la sfârșit. Calcularea întregului produs devine repede imposibilă într-un tip numeric obișnuit, dar zerourile pot fi numărate fără produs.

Un zero vine dintr-un factor 10

Fiecare factor 10 se descompune în 2·5. În factorial sunt cel puțin la fel de mulți factori 2 ca factori 5. Numărul perechilor 2·5 este deci dat de numărul factorilor 5. Nu numărăm cifrele zero din scrierea lui n, ci factorii primi din toate numerele înmulțite.

Multiplii lui 5 aduc câte un factor 5. Multiplii lui 25 mai aduc unul, deoarece 25=5². Multiplii lui 125 aduc încă unul. Pentru 30!, calculul este ⌊30/5⌋+⌊30/25⌋=6+1=7. Simbolul ⌊x⌋ înseamnă partea întreagă inferioară; aici împărțirea întreagă a numerelor naturale face exact acest lucru.

Împărțiri repetate, fără puteri

Citim 0≤n≤10^18. Împărțim copia lui n la 5 și adunăm câtul, apoi repetăm cu acel cât. Astfel obținem succesiv ⌊n/5⌋, ⌊n/25⌋ și celelalte valori necesare, fără să construim o putere care ar putea depăși tipul.

Multiplii lui 5 până la 30 aduc șase factori 5. Numărul 25 aduce încă unul. Totalul este șapte zerouri finale.Mărește schema ↗

#include <iostream>
using namespace std;
int main() {
    long long n; cin >> n;
    long long zerouri=0;
    while(n>0) {
        n/=5;
        zerouri+=n;
    }
    cout << zerouri << '\n';
}

De ce 25 se numără de două ori

La prima împărțire, 25 apare în grupul multiplilor lui 5. La a doua, apare în grupul multiplilor lui 25. Acest lucru nu dublează un obiect din greșeală: numărul 25 contribuie cu doi factori 5 diferiți în produs. Pentru 125 există trei contribuții.

Suma este mai mică decât n/4 pentru n pozitiv, prin comparație cu seria n/5+n/25+… . Pentru limita declarată, rezultatul încape în long long. Numărul de pași este O(log₅(n+1)), deoarece n se împarte la 5 la fiecare iterație. Memoria este O(1), un număr fix de variabile.

Exersează

Pentru 0, 4, 5, 10, 25 și 30, răspunsurile sunt 0, 0, 1, 2, 6 și 7. Compară 24! și 25!: numărul zerourilor crește de la 4 la 6, nu doar cu unu. Explică saltul folosind descompunerea lui 25. Ca extensie, urmărește saltul dintre 124! și 125!.

Revezi factorii primi, împărțirea întreagă și factorialul recursiv pentru a separa valoarea produsului de o proprietate a lui.

Întrebări frecvente

Cum număr zerourile de la sfârșitul lui n factorial?

Adună câturile întregi n/5, n/25, n/125 și așa mai departe, cât timp sunt nenule. Ele numără factorii 5 din produs, care formează factori 10 împreună cu factorii 2 disponibili.

De ce multiplii lui 25 contribuie cu două zerouri?

Un multiplu al lui 25 conține cel puțin doi factori 5. Este numărat o dată între multiplii lui 5 și încă o dată între multiplii lui 25. Factorii 2 necesari există în factorial.

Trebuie să calculez factorialul pentru a-i număra zerourile?

Nu. Numărarea factorilor 5 evită produsul foarte mare. Pentru 0!, valoarea este 1 și numărul zerourilor finale este 0.