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.
Răspunsuri la întrebare
Răspuns de
3
#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;
}
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;
}
Alte întrebări interesante
Limba română,
9 ani în urmă
Matematică,
9 ani în urmă
Matematică,
9 ani în urmă
Matematică,
9 ani în urmă
Limba română,
9 ani în urmă
Matematică,
9 ani în urmă
Limba română,
9 ani în urmă
Matematică,
9 ani în urmă