Enunțul problemei ucif, de clasa a 5-a, dată în 2005 la OJI, se găsește pe vArena.

Rezumat

Pentru un număr natural nenul $n$ mai mic decât $101$, să se afșeze ultima cifră a sumei:

$$s = 1^1+2^2+3^3+ \cdots + n^n$$

De exemplu, pentru $n = 3$, suma este $32$, iar ultima cifră a sa este $2$.

Soluție

Această problemă este un exercițiu foarte simplu, ce combină structura repetitivă cu ultima cifră a unui număr. Folosind un for, pentru fiecare i de la 1 la n calculăm ultima cifră a lui $i^i$ și o adunăm la sumă. Se știe că ultima cifră a lui x este x % 10. Deci, iată secvența de cod ce calculează ultima cifră a lui $i^i$:

u = 1;
for (j = 0; j < i; j++)
    u = u * i % 10;

Ca să adăugăm pe u la suma s, vom scrie s = (s + u) % 10;.

Se observă că algoritmul face $1 + 2 + \cdots + n = n(n + 1) / 2$ pași (mă refer la numărul de intrări în al doilea for). Asta înseamnă foarte puțin pentru restricția din problemă; nu e nevoie de cine știe ce optimizări.

Sursă C++

#include <fstream>

std::ifstream fin("ucif.in");
std::ofstream fout("ucif.out");

int n, s; // s == 0

int main() {
    int i, j, u;

    fin >> n;
    for (i = 1; i <= n; i++) {
        u = 1; // Inițializăm ultima cifră cu elementul neutru la înmulțire.
        for (j = 0; j < i; j++)
            u = u * i % 10;
        s = (s + u) % 10; // Actualizăm suma.
    }

    // Afișăm răspunsul:
    fout << s << '\n';

    fout.close();
    return 0;
}

Dacă ai vreo nedumerire cu privire la problema ucif, lasă un comentariu și te voi ajuta :)

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație!

PayPal