很大的模量 [英] Modulus of a very large number

问题描述

用户将使用标准输入输入2个整数x和y.您需要计算x模y的余数(x％y).

The user will input 2 integers, x and y, using standard input. You need to calculate the remainder of x modulo y (x % y).

现在，这是问题所在:

0< = x< = 10 ^ 100000，(这是小于或等于"而不是箭头). 0 ＜ y< = 100000

0 <= x <= 10^100000, (this is "less than or equal" not an arrow). 0 < y <= 100000

我们正在寻找最佳解决方案(时间复杂度).

We are looking for optimal solution (Time Complexity).

我没有找到关于Stackoverflow的答案，所以找到解决方案后，我认为我应该在这里提出这个问题，以备将来参考，看看是否有更好的方法.

I didn't find the answer on Stackoverflow, so after finding the solution I thought that I should pose this question here for future reference and to see if there are better ways.

推荐答案

BigInteger 具有

BigInteger has the divideAndRemainder(...) method, one that returns a BigInteger array, the first item the division result, and the second, the remainder (which is what mod really does in Java).

更新

包括Mark Dickinson对其他答案的评论:

Including comment by Mark Dickinson to other answer:

有一个简单得多的线性时间算法:将acc设置为0，然后依次对x中的每个数字d(从左到右)，将d转换为整数，并设置acc =(acc * 10 + d)％y .一旦数字被消耗掉，acc就是您的结果.

There's a much simpler linear-time algorithm: set acc to 0, then for each digit d in x in turn (left to right), convert d to an integer and set acc = (acc * 10 + d) % y. Once the digits are consumed, acc is your result.

按照说明实施了所有3种算法:

Implemented all 3 algorithms as described:

private static int testMarkDickinson(String x, int y) {
    int acc = 0;
    for (int i = 0; i < x.length(); i++)
        acc = (acc * 10 + x.charAt(i) - '0') % y;
    return acc;
}

private static int testHovercraftFullOfEels(String x, int y) {
    return new BigInteger(x).divideAndRemainder(BigInteger.valueOf(y))[1].intValue();
}

private static int testMrM(String x, int y) {
    String s = x;
    while (s.length() >= 7) {
        int len = Math.min(9, s.length());
        s = Integer.parseInt(s.substring(0, len)) % y + s.substring(len);
    }
    return Integer.parseInt(s) % y;
}

使用种子随机数进行测试以进行可验证的测试(不想对98765数字进行硬编码):

Testing with seeded random number for verifiable test (didn't want to hardcode a 98765 digit number):

public static void main(String[] args) {
    Random r = new Random(98765);
    char[] buf = new char[98765];
    for (int i = 0; i < buf.length; i++)
        buf[i] = (char)('0' + r.nextInt(10));

    String x = new String(buf);
    int y = 98765;

    System.out.println(testMarkDickinson(x, y));
    System.out.println(testHovercraftFullOfEels(x, y));
    System.out.println(testMrM(x, y));

    long test1nano = 0, test2nano = 0, test3nano = 0;
    for (int i = 0; i < 10; i++) {
        long nano1 = System.nanoTime();
        testMarkDickinson(x, y);
        long nano2 = System.nanoTime();
        testHovercraftFullOfEels(x, y);
        long nano3 = System.nanoTime();
        testMrM(x, y);
        long nano4 = System.nanoTime();
        test1nano += nano2 - nano1;
        test2nano += nano3 - nano2;
        test3nano += nano4 - nano3;
    }
    System.out.printf("%11d%n%11d%n%11d%n", test1nano, test2nano, test3nano);
}

输出:

23134
23134
23134
    8765773
 1514329736
 7563954071

这3个都产生了相同的结果，但是在性能上有明显的区别，M先生的更好的解决方案"是所有这些中最差的.

All 3 produced same result, but there's a clear difference in performance, and Mr. M's "better solution" is the worst of them all.

这篇关于很大的模量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！