Szybkie potegowanie modulo

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;
}

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 16⁸ przez 16⁸ wychodzi ci 16¹⁶, czyli 2⁶⁴, czyli liczba niemieszcząca się w zakresie twojego unsigned long long, wrapująca się do zera.

niestety trzeba bedzie wlasną artmetyke zaimplementowac :(

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.

jedrzejd napisał(a):

niestety trzeba bedzie wlasną artmetyke zaimplementowac :(

Moze niekoniecznie: www.gmplib.org

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

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

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

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:https://wandbox.org/permlink/Qpo1ZKCk9u5zi106
Trzeba zaimplementować potęgowanie modulo tu masz opis: http://eduinf.waw.pl/inf/alg/001_search/0017.php#A1

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