Проблема модульного экспонирования в Java

Question

import java.util.Scanner;

class codeabbey145 
{
    public static void main(String[] Args)  
    {
        Scanner input = new Scanner(System.in);
        double A = 0;
        double B = 0;
        double M = 0;
        System.out.println("\n\nHow many sets?");
        int s = input.nextInt();
        double X[] = new double[s];
        for(int i = 0; i<s; i++)
        {
            System.out.println("A: ");
            A = input.nextDouble();
            System.out.println("B: ");
            B = input.nextDouble();
            System.out.println("M: ");
            M = input.nextDouble();
            X[i] = (Math.pow(A, B)) % M;  //(A^B)%M
        }
        for(int j = 0; j<s; j++)
        {
            System.out.print(Math.round(X[j]) + " ");
        }
    }
}

Я пытался выполнить упражнение 145 на Codeabbey.com

Формула, приведенная для модульного возведения в степень: (A^B)%M

Я старался изо всех сил внедрить эту формулу в мой код, но ответы, которые я получал, неверны. Кто-нибудь знает, почему это может быть?

заранее спасибо

Answer 1

Ваш код абсолютно правильный: проверьте здесь.

Вероятно, вы должны использовать BigInteger: для обработки больших чисел double никогда не рекомендуется.

Вот рабочий пример: проверьте это демо

Код

public static void main(String[] Args) {
        Scanner input = new Scanner(System.in);

        System.out.println("\n\nHow many sets?");
        int s = input.nextInt();
        BigInteger[] X = new BigInteger[s];
        for (int i = 0; i < s; i++) {
            System.out.println("A: ");
            BigInteger A = input.nextBigInteger();
            System.out.println("B: ");
            BigInteger B = input.nextBigInteger();
            System.out.println("M: ");
            BigInteger M = input.nextBigInteger();
            X[i] = A.modPow(B, M); //(A^B)%M
        }
        for (int i = 0; i < X.length; i++) {
            System.out.println(X[i]);
        }
    }

Я пытался этот вопрос на CodeAbbey. Мое решение было принято.

Код:

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main(String[] Args) {
        Scanner input = new Scanner(System.in);
        int s = input.nextInt();
        BigInteger[] X = new BigInteger[s];
        for (int i = 0; i < s; i++) {
            BigInteger A = input.nextBigInteger();
            BigInteger B = input.nextBigInteger();
            BigInteger M = input.nextBigInteger();
            X[i] = A.modPow(B, M);
        }
        for (int i = 0; i < X.length; i++) {
            System.out.println(X[i]+" ");
        }
    }
}

Answer 2

Скорее всего, значения слишком велики, чтобы вписаться в double поэтому они переполняются. Ваш лучший выбор, вероятно, заключается в использовании BigInteger объекты.

BigInteger имеет pow а также mod функции, которые вы можете использовать для своих расчетов.