Rezolvare completă PbInfo #843 Puteri2

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Puteri2:

#include <iostream>
using namespace std;

int a , n , p;
int p10;

int putere(int a ,int n)
{
    if(n == 0)
        return 1;
    if(n % 2 == 1)
    {
        long long tmp = putere(a , n - 1);
        tmp *= a;
        return tmp % p10;
    }
    else
    {
        long long tmp = putere(a , n / 2);
        return (tmp * tmp) % p10;
    }
}

int main(){
    cin >> a >> n >> p;
    p10 = 1;
    for(int i = 1 ; i <= p ; i ++)
        p10 *= 10;
        
    cout << putere(a , n);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #843 Puteri2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #843 Puteri2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!