java - 如果 c 比 b 小得多，找到 a**b % c(a 幂 b 模 c)的最佳方法是什么？

Question

我已经在 java 中为 BigInteger 尝试过 modPow() 函数。
但它需要太长时间。

我知道模乘法，甚至也知道求幂。

但由于条件限制，我无法解决这个问题。

a、b 的值可以包含 1000000 个数字(这么大，不是吗)？现在我想找到 (a**b)%c。作为第一步，我们可以做 a = a % c。但是在这里，即使是 b 也是如此巨大。

c = 10^9+7

Answer 1

尝试使用此功能。它使用一些 JS 引擎来计算任何东西。将表达式作为字符串参数并运行它。

private void calculateExpression(String exp){

    try {
        //calling a JS engine which helps us to calculate what we need
        ScriptEngineManager mgr = new ScriptEngineManager();
        ScriptEngine engine = mgr.getEngineByName("JavaScript");
        Object result = engine.eval(exp);

        //checking if we got any error
        if (result.toString().equals("Infinity") || result.toString().equals("NaN")){
            System.out.println("Can't divide with zero");
        }           
        else if (result != null){
            Double doubleResult = new Double("" + result);

            //checking if the result is an int value
            if ((doubleResult == Math.floor(doubleResult)) && !Double.isInfinite(doubleResult)) {
                text.setText("" + (doubleResult.longValue()));
            }
            else {
                //means that it's double value
                text.setText(result.toString());
            }
        }
    }
    catch (Exception e) { 
        e.printStackTrace();
    }
}