Wątek przeniesiony 2017-08-02 10:39 z Kariera przez somekind.

Czy umiesz potęgować?

0

Cześć! Pomożecie mi z tym problemem? Daje link do zadania http://pl.spoj.com/problems/PA05_POT/ ogólnie chodzi o to, aby program wyznaczał dla D przypadków ostatnią cyfrę potęgi b liczby a,
a gdy próbuje dodać rozwiązanie na stronke to dostaje komunikat, że odpowiedź jest błędna, co zrobiłem nie tak? Dajcie jakieś małe wskazówki, z góry dziękuje! :)

#include<iostream>
int a;
int b;
int c;
int D;
int potega(int a,int b)
{
    if (b==0)return 1;
    else
    return a=a*potega(a,--b);
}
using namespace std;
int main()
{
    cin>>D;
    while(D>0)
    {
        cin>>a>>b;
        b = b%4;
        if(b==0)
        b=4;
        a=a%10;
        cout<<potega(a,b)%10;
        D--; 
    }
    return 0;
}
1

To co napisałeś nie ma najmniejszego sensu. Po pierwsze dlatego że nie rozumiesz jak duże liczby tutaj masz i jak przechowywane są w komputerze. Zmienna int ma 32 bity wiec przechowa nie więcej niż 2^32 z definicji. A ty masz liczby rzędu miliard^miliard.
A juz to twoje liczenie *potęgi rekurencyjnie to wisienka na torcie :D
Zastanów się czy musisz znać cała liczbę żeby poznać jej ostatnią cyfrę. Przeczytaj też https://en.wikipedia.org/wiki/Modular_exponentiation

0

Masz prawie dobrze. Zrób tylko:
a) wywal czwórki
b) zamień potega() na potega_mod10()
c) usuń rekurencję
d) zaimplementuj potega_mod10()

1

Temat lekcji na dzisiaj: szybkie potęgowanie modularne. Proszę wygooglać.

PS.
Zły dział.

1

@enedil: Masz rację, nawet znalazłem swoje rozwiązanie. Teraz już wiem o co chodziło z tą 4 koledze - cykle

import sys
matrix = [
    ["1\n","1\n","1\n","1\n"],
    ["2\n","4\n","8\n","6\n"],
    ["3\n","9\n","7\n","1\n"],
    # reszta do policzenia przez autora
]

test_count = int( sys.stdin.readline() )
for test_num in xrange(0, test_count):
    input = sys.stdin.readline().split(' ')
    sys.stdout.write( matrix[(int(input[0])-1)%10][(int(input[1])-1)%4] )

Bez tablicowania, biorąc pod uwagę jedynie cykl:

tests = int(raw_input())
for test_num in xrange(0, tests):    
    a, b = map(int, raw_input().split())
    a, b = a%10, 1 + (b-1)%4
    print  (a**b) % 10
0

Jest jeszcze bardziej uniwersalne potęgowanie modulo (bez tablicowania):
http://www.algorytm.org/algor[...]ie-potegowanie-modularne.html

0

Wychodzi na to, że miał prawie dobrze (pomijając rekurencję), tylko źle policzył b.

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