Szybkie potegowanie modulo

0

Witam czy może znacie rozwiazanie problemu :
Czemu szybkie potegowanie modulo daje złą odpowiedz na 16^16 mod 10^18
o to kod

unsigned long long pot_szybkie(unsigned long long a,unsigned long long n,unsigned long long q){
    unsigned long long w=1;
    while(n>0){
        if (n%2==1)w=(w*a)%q;
        a=(a*a)%q;
        n/=2;
    }
    return w%q;
}
0

Jaką daje? Jakiej się spodziewasz? Polecam lekturę: https://dsp.krzaq.cc/post/445/jak-zadawac-pytania-na-forum/

Tutaj zapewne problemem jest to, że mnożąc 168 przez 168 wychodzi ci 1616, czyli 264, czyli liczba niemieszcząca się w zakresie twojego unsigned long long, wrapująca się do zera.

0

niestety trzeba bedzie wlasną artmetyke zaimplementowac :(

0

To jakieś zadanie, że będziesz musiał? Na szybko możesz Boost.Multiprecision użyć:

using bigint_t = boost::multiprecision::uint1024_t;

bigint_t pot_szybkie(bigint_t a,bigint_t n,bigint_t q){
    bigint_t w=1;
    while(n>0){
        if (n%2==1)w=(w*a)%q;
        a=(a*a)%q;
        n/=2;
    }
    return w%q;
}

https://wandbox.org/permlink/g9zsJMEXNhci3HpT

Na mniej szybko i poprawniej, patrz na odpowiedź @lion137 niżej.

0
jedrzejd napisał(a):

niestety trzeba bedzie wlasną artmetyke zaimplementowac :(

Moze niekoniecznie: www.gmplib.org

0

tylko ze to zadanko z algo i niewiem czy to tak mozna

2

To Moze Zajrzyj tutaj//en.m.wikipedia.org/wiki/Modular_exponentiation

0

Użyj square and multiply po prostu.

    def square_and_multiply(base, exponent, modulus):
        binary_exponent = to_binary(exponent)
        result = 1
        for di in binary_exponent:
            square = result * result
            if di == 0:
                result = square % modulus
            else:
                result = (square * base) % modulus
        return result
1

problemem jest a=(a*a)%q; a konkretniej a*a już ci wykroczy poza zakres i dzielenie mordulo już jest wykonywane na złej wartości.
Dowód//wandbox.org/permlink/Qpo1ZKCk9u5zi106
Trzeba zaimplementować potęgowanie modulo tu masz opis: http://eduinf.waw.pl/inf/alg/001_search/0017.php#A1

0

Jeśli wiesz, że modulus jest liczbą złożoną, to możesz skorzystać z Chińskiego Twierdzenia o Resztach. Załóżmy, że n = a*b, gdzie a, b są względnie pierwsze. Wówczas wartość (x^y)%n możesz otrzymać z (x^y)%a oraz (x^y)%b za pomocją rozszerzonego algorytmu Euklidesa.

Edycja: hmm, skoro to contest algorytmiczny, to zapewne modulus będzie liczbą pierwszą :c

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