Question

Fie operaţia a n =a*a*...*a , produsul având n factori. Efectuând înmulţirile de la stânga la dreapta, se vor face n-1 înmulţiri. Numărul de înmulţiri necesar pentru a calcula a n este mult mai mic dacă folosim următoarele observaţii:


a n = a * a n-1 , dacă n este impar.

a n = ( a n/2)2 , dacă n este par.

Cerința

Se dau numerele naturale a n p. Calculați determinaţi numărul format din ultimele p cifre ale alui a n.


Date de intrare

Programul citește de la tastatură numerele a n p.


Date de ieșire

Programul va afișa pe ecran numărul X, valoarea cerută.


Restricții și precizări

1 ≤ a ≤ 1000

1 ≤ n ≤ 1.000.000.000

1 ≤ p ≤ 5




Exemplu

Intrare


2 16 3

Ieșire


536

Explicație

2 16 este 65536, iar numărul format din ultimele 3 cifre este 536.

Answer 1

Răspuns:

#843 Puteri2

Explicație:

#include <iostream>

using namespace std;

long long a,n,p,z=1, num, X;

long long putere(long long n)

{

   if (n==0) return 1;

   else

   {

       if (n%2) return (a%z)*(putere(n-1)%z);

       else return (putere(n/2)%z)*(putere(n/2)%z);

   }

}

int main()

{

   cin >> a >> n >> p;

   while (p)

   {

       z=z*10; --p;

   }

   cout << putere(n)%z;

}