Вычисление 2 ^ n% k с использованием только целых чисел

Question

Мне нужно написать код, который получает 2 переменные (n, k) и выводит ответ в виде (2 ^ n)% k.

Я могу использовать только целые числа, без методов, без массивов, безматематикаи так далее. пока у меня есть это:

int n = myScanner.nextInt();  
    int k = myScanner.nextInt();   
    int num = 1;
    int modulo = 1;
    for (int i = 0; i < n; i++) {    
            num = num * 2;  
            modulo *= 2%k;

    }

    modulo = modulo%k;
    System.out.println(modulo);

проблема заключается в диапазоне самого int, не превышает 2 ^ 31 ... но все же мне нужно, чтобы он работал как-то, любая помощь будетбыть очень ценным!

Answer 1

Вы имеете дело с Модульным возведением в степень . Одно из возможных решений - избежать умножения на большие числа, которое переполнит int, используя следующие преимущества:

При заданных двух целых числах a и b следующие два уравнения эквивалентны:

c mod m = (a ⋅ b) mod m

c mod m = [(a mod m) ⋅ (b mod m)] mod m

InJava простое решение, основанное на алгоритме, объясненном в этом разделе :

int mod(int base, int exponent, int modulus) {
  if (modulus == 1) return 0;
  int c = 1;
  for (int i = 0; i < exponent; i++) {
    c = (c * base) % modulus;
  }
  return c;
}

Answer 2

Если ваша проблема в том, что он не может хранить больше 2 ^ 31, это потому, что вам нужно использовать длинный тип данных для хранения значения. Long может хранить максимальное значение 2 ^ 63 (подписано).