Повышение числа до огромного показателя

Question

Мне дано число 3 и переменная 'n', которая может достигать 1 000 000 000 (миллиардов).Я должен напечатать ответ 3^n modulo 100003.Я попробовал следующее:

1. Я попытался использовать функцию std::pow(3,n), но она не работает для больших показателей (не может применить модуль по ходу процесса).
2. Я пытался реализовать свою собственную функцию, которая бы поднимала число 3 до степени n, чтобы я мог применять модуль по мере необходимости, но при тестировании с очень большими числами этот метод оказался слишком медленным.

3. Наконец, я попробовал простую факторизацию числа 'n' и затем использовал факторы 'n' (и сколько раз они появляются), чтобы построить ответ, и это кажется лучшим методом, который я мог бы придумать (если онправильный).Проблема в том, что бы я сделал для огромного числа, которое уже является простым?

   Так что это были мои идеи, если кто-то думает, что есть лучший способ (или если один из моих методов является оптимальным), ябыл бы признателен за любые рекомендации.

Answer 1

Это усиливает ответ Кайдула.

100003 - это простое число, которое немедленно приводится в Маленькой теореме Ферма : любое число, возведенное в простую степень, конгруэнтно себе по модулю этого простого числа. Это означает, что вам не нужно повышать до n -ой силы. A n % 100002 достаточно мощности.

Редактировать: пример.

Скажем, n - это 200008, то есть 100002 * 2 + 6. Сейчас

3 ^ 200007 =
3 ^ (100002 + 100002 + 6) = 
3 ^ 100002 * 3 ^ 100002 * 3 ^ 6

FLT утверждает, что (3 ^ 100002) % 100003 == 1, и последняя строка выше, по модулю 100003, уменьшается до 3 ^ 6. В общем, для простого p,

(k ^ n) % p == k ^ (n % p)

Конечно, это только ускоряет вычисления, если показатель n больше p. По вашему запросу (показатель 100, по модулю 100003) уменьшать нечего. Идите прямо к подходу Кайдула.

Answer 2

Воспользуйтесь свойством модульной арифметики

(a × b) modulo M == ((a module M) × (b modulo M)) modulo M

Используя указанное выше правило умножения

(a^n) modulo M 
= (a × a × a × a ... × a) modulo M 
= ((a module M) × (a modulo M) × (a modulo M) ... × (a modulo M)) modulo M

Рассчитать результат методом разделяй и властвуй. Отношение повторения будет:

f(x, n) = 0                     if n == 0

f(x, n) = (f(x, n / 2))^2       if n is even
f(x, n) = (f(x, n / 2))^2 * x   if n is odd

Вот реализация C ++:

int powerUtil(int base, int exp, int mod) {
    if(exp == 0) return 1;
    int ret = powerUtil(base, exp / 2, mod) % mod;
    ret = 1LL * ret * ret % mod;
    if(exp & 1) {
        ret = 1LL * ret * base % mod;
    }
    return ret;
}

double power(int base, int exp, int mod) {
    if(exp < 0) {
        if(base == 0) return DBL_MAX; // undefined
        return 1 / (double) powerUtil(base, -exp, mod);
    }
    return powerUtil(base, exp, mod);
}