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

#include <bits/stdc++.h>
using namespace std;
int m, p, cif, i, nr;
int exp(int a, int n)
{
if(n == 0) return 1;
if(n % 2 == 1)
{
long long tmp = exp(a, n - 1);
tmp = tmp * a;
return tmp % nr;
}
else
{
long long tmp = exp(a , n / 2);
return (tmp * tmp) % nr;
}
}


int main()
{
    cin>>m>>p>>cif;
    nr = 1;
    for(i=1;i<=cif;i++)
        nr = nr * 10;
    cout << exp(m, p);
    return 0;
}