Ostatnia cyfra liczby a poniesionej do potęgi b

Witam.

Mam pewien problem. Chce obliczyć ostatnią cyfrę liczby a poniesionej do potęgi b. Zwykłe potęgowanie było by głupie, więc postanowiłem wykorzystać własności działań modulo. Program działa poprawnie dla większości danych wejściowych jednakże czasem wyniki są błędne. Nie bardzo wiem gdzie tkwi mój błąd.

int mod10(int a, int b){
    int wyjs = 0; int c = 1;
    
    while( !(b==1 || a==1 || a==-1 || a==-9 || a==9 || a==0)){
        if(b%2){
            c *= a % 10;
            a = (a * a) % 10;
            b /= 2;
        } else {
            a = (a * a) % 10;
            b /= 2;
        }
    }
    
    if(b==1){
        wyjs = (c % 10) * (a % 10) % 10;
    } else {
        if(b%2){ b=0; } else { b=1; }
        switch(a){
            case -1: if(b){ wyjs = 1; }else{ wyjs = 9; } break;
            case -9: wyjs = 1; break;
            case 1: wyjs = 1; break;
            case 9: if(b){ wyjs = 1; }else{ wyjs = 9; } break;
            case 0: wyjs = 0; break;
        }
    }
    return (c*wyjs)%10;
}

Ale nakombinowałeś !!!

char pow_cyfra(int base,unsigned p)
  {
   if(!p) return '1';
   if(base<0) base=-base;
   int pow=1;
   for(base%=10;p;p>>=1)
     {
      if(p&1) pow=(pow*base)%10;
      base=(base*base)%10;
     }
   return (char)('0'+pow);
  }

I nic więcej.

ups...

Jeżeli chodzi o ostatnią cyfrę potęgi, to ja bym sprawdził, czy może nie jest ona w pewnym stopniu okresowa.

Zawsze można sobie stablicować wyniki :P

#include <cstdlib>
#include <iostream>

int a0[] = {0};
int a1[] = {1};
int a2[] = {2, 4, 8, 6};
int a3[] = {3, 9, 7, 1};
int a4[] = {4, 6};
int a5[] = {5};
int a6[] = {6};
int a7[] = {7, 9, 3, 1};
int a8[] = {8, 4, 2, 6};
int a9[] = {9, 1};

int *powers[] = {a0, a1, a2, a3, a4, a5, a6, a7, a8, a9};
int powerPeriods[] = {1, 1, 4, 4, 2, 1, 1, 4, 4, 2};

int fun(int a, int b) {
    int lastDigit = a % 10;
    return b == 0 ? 1 : powers[lastDigit][(b - 1) % powerPeriods[lastDigit]];
}

int main(int argc, char** argv) {

    int a, b;

    std::cin >> a >> b;

    std::cout << fun(a, b) << std::endl;

    return EXIT_SUCCESS;
}

A jeśli nawet nie, to można na piechotę policzyć te okresy, które tu stablicowałem. Tak czy siak można się zamknąć w czasie O(1) (zakładając, że postawa systemu liczenia jest stała).

PS:
Kod jest WTFem bo zapomniałem C++'a :P

Heh przekombinowałem :D dzięki za odpowiedzi ;)

_13th_Dragon napisał(a)

Ale nakombinowałeś !!!

char pow_cyfra(int base,unsigned p)
  {
   if(!p) return '1';
   if(base<0) base=-base;
   int pow=1;
   for(base%=10;p;p>>=1)
     {
      if(p&1) pow=(pow*base)%10;
      base=(base*base)%10;
     }
   return (char)('0'+pow);
  }

I nic więcej.

Przy wywołaniu pow_cyfra(3,3) otrzymuje 55 zamiast 7

Przepraszam, przetestowałem na szybko i nie zwróciłem uwagi. Dzięki za wskazówkę ;). Temat do zamknięcia