Problema Ucif

Fie n un numar natural si s suma urmatoare:

s = 11+ 22 + 33 + … + nn

Cerinta

Scrieti un program care sa afiseze ultima cifra a lui s.

Date de intrare

De pe prima linie a fisierului de intrare ucif.in se citeste numarul n

.

Date de iesire

Pe prima linie a fisierului de iesire ucif.out se va afisa numai ultima cifra a lui s.

Restrictii

0 < n < 101

Exemplu:

ucif.in

3

ucif.out

2

Descrierea solutiei

Am abordat problema incercand sa fac ridicarea la putere in timp logaritmic, lucru care a fost foarte bun. Pentru solutia de mai joc, timpii sunt mai buni decat solutia oficiala, iar rezolvarea zic eu, daca nu mai simpla, cel putin mai eficienta. Timpul este peste tot 0 . 😀

Solutie

#include <iostream>
#include <fstream>
using namespace std; 

long long n,p,i,S;
long long tip;
long long put(long n, long p) 
{
 if(p==0) return 1;
 if(p%2==1)
 return (n*put(n,p-1))%10; 
 tip=put(n,p/2)%10;
 return tip*tip%10;
}  

int main()
{
 ifstream f("ucif.in");
 ofstream g("ucif.out");
 f>>n;
 f.close();
 for(i=1;i<=n;++i)
 {
 p=i;
 S+=put(i,p);
 }
 g<<S%10;
 g.close();
 return 0;
}