java - 在 C 和 Java 中使用哪种数据类型来计算数字的模逆？

Question

我完成了下面提到的教程，并尝试在 C 和 Java 中计算数字的模逆，但在这两种情况下，我得到的输出都是 0，请指导我纠正我的代码。

https://www.hackerearth.com/practice/math/number-theory/multiplicative-inverse/tutorial/

import java.lang.Math;
import java.util.*;
import java.math.BigInteger;
import java.math.BigDecimal;
class TestClass {
    public static void main(String args[] ) throws Exception {
       Scanner sc=new Scanner(System.in);
       int a=sc.nextInt();
       BigInteger bi=BigInteger.valueOf(a);
       BigInteger k = new BigDecimal(Math.pow(10,9)).toBigInteger();
       BigInteger b=k.add(BigInteger.valueOf(7));
       BigInteger c=b.subtract(BigInteger.valueOf(2));
       BigInteger m=bi.modPow(c,BigInteger.valueOf(1));
       BigInteger d=m.mod(b);
       System.out.println(d);

    }
}

在 C 语言中，

#include <stdio.h>
#include<inttypes.h>
#include<math.h>
int main()
{
    uintmax_t a;
    scanf(" %ju",&a);
    uintmax_t b=pow(10,9);
    uintmax_t m=b+7;
    uintmax_t c=((uintmax_t)pow(a,m-2))%(m);
    printf("%ju",c);
    return 0;
}

我无法了解溢出背后的原因，请澄清这一点。

Answer 1

你的java代码不起作用的原因是

BigInteger m=bi.modPow(c,BigInteger.valueOf(1));

计算 bi^c mod 1，对于任何 bi 和 c 均为 0。

你要计算的是bi^c mod b，编码为

BigInteger m = bi.modPow(c, b);

<小时/>

由于 C 没有 powmod 函数，您需要自己编程。

以下函数计算x^e mod m:

uintmax_t powmod(uintmax_t x, uintmax_t e, uintmax_t m) {
    uintmax_t result = 1;
    while (e > 0) {
        if (e&1) {
            result = result * x % m;
        }
        x = x * x % m;
        e >>= 1;
    }
    return result;
}