Problem z zadaniem ze SPOJa, "czy umiesz potegowac"

0

Czesc, mam problem z zadaniem, sedzia mowi mi, ze uzyskal bledna odpowiedz a ja nie moge sie dopatrzyc bledu, pomozcie

link do zadania: http://pl.spoj.com/problems/PA05_POT/

#include <cstdlib>
#include <iostream>
using namespace std;

int main()
{
int t;
int a, b,tmp;
cin>>t;
for(int i=0;i<t;i++)
{
    cin>>a>>b;
    tmp=a%10;
    int x=b%4;
    if(x==1)
    {
        cout<<a%10<<endl;
    }else if(x==0)
    {
        cout<<(tmp*tmp*tmp*tmp)%10<<endl;
    }else
    {
    for(int j=1;j<x;j++)
    {
        a*=tmp;
    }
    cout<<a%10<<endl;
    }

}

 system("pause");
 return 0;
}
0

Wychodzisz wartościami poza zakres zmiennych. Aby rozwiązać zadanie musisz zauważyć schematyczność występowania odpowiedniej wartości jako ostatniej cyfry.

0

Przeanalizuj sobie powtarzające się wzory, w zależności jaka jest ostatnia cyfra liczby podnoszonej do potęgi; szczęśliwie one się powtarzają z okresem maksymalnie 4. Czyli, łatwo znaleźć zależność modulo dająca ostatnią cyfrę, w zalezności od ostataniej cyfry liczby potęgowanej. Złożoność będzie stała, plus złożoność modulo, pseudokod:

fun las_digit(n, k):
    if n % 10 == 0:
        return 0
    if n % 10 == 1:
        return 1
    if n % 10 == 5:
        return 5
    if n % 10 == 6:
        return 6
    if n % 10 == 2:
        digits = [2, 4, 8, 6]
        tmp_rest = k % 4
        if tmp_rest == 0:  ## Jak dzieli się bez reszty to wzór powtórzy się jakieś m razy 4 czyli ostatnia cyfra: 
            return digits[-1]  ## by convention array[-1] returns the last intem in the array
        else:
            return digits[tmp_rest - 1] ## jak nie to zwracam kolejne z tablicy (reszta) ( -1, bo indeksowanie od 0)
    if n % 10 == 3:
        digits = [3, 9, 7, 1]
        tmp_rest = k % 4
        if tmp_rest == 0:
            return digits[-1]
        else:
            return digits[tmp_rest - 1]
    if n % 10 == 4:
        digits = [4, 6]
        tmp_rest = k % 2
        if tmp_rest == 0:
            return digits[-1]
        else:
            return digits[tmp_rest - 1]
    if n % 10 == 7:
        digits = [7, 9, 3, 1]
        tmp_rest = k % 4
        if tmp_rest == 0:
            return digits[-1]
        else:
            return digits[tmp_rest - 1]
    if n % 10 == 8:
        digits = [8, 4, 2, 6]
        tmp_rest = k % 4
        if tmp_rest == 0:
            return digits[-1]
        else:
             return digits[tmp_rest - 1]
    if n % 10 == 9:
        digits = [9, 1]
        tmp_rest = k % 2
        if tmp_rest == 0:
            return digits[-1]
        else:
            return digits[tmp_rest - 1]
0

Dzieki wielkie, ogarnalem :D

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0