Question

Care este ultima cifra nenula a produsului
1*2*3*4*5*...*n, n fiind un numar format din cel mult 9 cifre ?

Answer 1

Răspuns:

#include <iostream>

using namespace std;

int main(){

   int n;

   cin >> n;  

   int d2 = 0, d5 = 0, p = 1;

   for(int i = 1 ; i<=n ; ++i)

   {

       int m  = i;

       while(m % 5 == 0)

           m /= 5, d5++;

       while(m % 2 == 0)

           m /= 2, d2++;

       p = (p * m) % 10;

   }

   int k = d2-d5;

   for(int i = 1 ; i<=k ; ++i)

       p = (2*p) % 10;

   cout << p;

   return 0;

}

Explicație:

- Numarul de zerouri de la sfarsitul lui n! este egal cu numarul de perechi 2*5.

- Numarul de 2 (d2) din n! este mai mare decat numarul de 5 (d5) din n!

- Se elimina din fiecare termen al produsului divizorii 2 si 5, iar la sfarsit numarul se reface prin inmultirile cu 2 de (d2 - d5) ori

- (p1 * p2 * p3 * ....* pk) % 10 = ((((p1 % 10) * p2) % 10) *....) * pk) % 10