Блог

https://practice.geeksforgeeks.org/problems/abset-2/0 / , это вопрос gfg, в котором меня просят вывести мое число (a ^ b) по модулю 10 ^ 9 7.

итак, вот мой первый код;

 public static void main (String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t--!=0){
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int result = 1;
        
        for(int i = 0; i<b; i  ){
            result = result*a;
            
        }
        System.out.println(result%1000000007);
    }
}
  

и это не дает правильного вывода для 99 ^ 928. Затем я изменил тип данных результата на long, даже если это дает отрицательное число. Затем мне пришлось изменить свой код следующим образом, и это сработало

 public static void main (String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t--!=0){
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        long result = 1;
        
        for(int i = 0; i<b; i  ){
            result = (result*a);
            result = result%1000000007;
        }
        System.out.println(result);
    }
  

здесь мой вопрос заключается в том, когда я ввел результат% 1000000007 в цикл for, как это сработало, в соответствии с проблемой, разве я не должен был выводить конечный результат модулем 10 ^ 9 7?

int и long имеют максимальные значения. В зависимости от того, a и b a^b превышает этот максимум и переполняется.

Операция по модулю в конце приведет к неправильному значению переполнения, и результат будет отключен.

Особенность modulo заключается в том, что вы можете применять modulo во время вычислений в основном, когда захотите, без изменения результата. (a b) mod m имеет то же значение, что и (a mod m b mod m) mod m , и аналогично (a * b) mod m совпадает с (a mod m * b mod m) mod m , то есть просто работает оператор по модулю. Просто поиграйте с несколькими небольшими значениями a b и m на бумаге, чтобы убедиться, что правила работают.

Для заданий, включающих ОГРОМНЫЕ значения, очень типично быть вычислимым, только если вы добавляете некоторые mod m шаги где-нибудь в миксе (при условии, что они имеют смысл).

99 ^ 928 — это большое число с 1852 цифрами. Примитивные типы данных int и long в Java не имеют емкости для хранения такого числа: наибольшее значение, которое вы можете сохранить в int, равно 2147483647, а наибольшее, которое вы можете сохранить в long, равно 9223372036854775807. Операции, возвращающие большие значения, обтекаются, возвращая значение, правильное по модулю в степени 2, но совершенно непригодное для большинства практических целей.

Если бы вы распечатали промежуточные значения, вы бы увидели, что результат уже равен 99 ^ 10:

• 99^9 = 913517247483640899
• 99^10 = -1795512867667309079

Это означает, что если вы будете ждать выполнения операции по модулю до последнего момента, вы получите значение по модулю неправильного промежуточного результата. Вы должны контролировать, насколько большими получаются значения, используя modulo уже на промежуточных этапах.

Обратите внимание, что в Java есть классы для работы с целыми числами, размер которых больше, чем помещается в long: java.math.BigInteger . В нем даже есть удобный и быстрый метод для операции «модульного питания», которую вы реализуете:

 BigInteger base = BigInteger.valueOf(1000000007);
BigInteger result = BigInteger.valueOf(a).modPow(BigInteger.valueOf(b), base);