2020年4月4日 07:16:26go评论89阅读模式

英文:

Find value of n^k modulo 10^7 + 7

问题

给定整数 n 和 k，请找出 n^k 对 10^7+7 取模的值。我一直在尝试以不同的方式解决这个问题，利用取模运算的性质，即 (a * b) % c = ((a % c) * (b % c)) % c。以下是我的代码。另外，我是一个新用户，如果我漏掉了什么，请告诉我。

int res = 1;
int modulo = (int) Math.pow(10, 7) + 7;
//(a * b) % c = ((a % c) * (b % c)) % c
System.out.println(modulo);
for (int i = 1; i <= k; i++){
    res = ((res % modulo) * (n % modulo)) % modulo;
}
    
return res;

英文:

Giving int n and k. Find the value of n^k modulo 10^7+7.
I 've been trying to do this problem in different ways using the properties of modulo as ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c . Below is my code. Also, I am a new user, if I missed anything please let me know.

int res = 1;
int modulo = (int) Math.pow(10,7)+7;
//( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
System.out.println(modulo);
for (int i = 1 ; i &lt;= k; i++){
    res = ((res%modulo)*(n%modulo))%modulo;
   
}
return res;

答案1

得分: 1

下面两种解决方案的时间复杂度为_O(log k)_，与问题中的代码(O(k))和WJS的答案使用BigInteger（大整数）不同。当k为6位数时，WJS的代码开始变慢。下面两种解决方案即使在k为Long.MAX_VALUE时也会立即返回。

在本答案的描述中，a^b表示指数运算，而不是按位异或。

你已经在正确的路径上，使用了以下等式：

(a * b) % c = ((a % c) * (b % c)) % c

你所忽略的是：

a ^ (b + c) = (a ^ b) * (a ^ c)

递归解法

由于目标是计算(n^k) % (10^7 + 7)，你可以通过递归地分割k来在_O(log k)_时间内计算这个值。

例如，如果k = 15，那么可以这样分割：

n^15  =  n^8 * n^7
      =  (n^4 * n^4) * (n^4 * n^3)
      =  ...

用模运算表示：

(n^15) % m  =  ((n^8) % m * (n^7) % m) % m
            =  ...

如果你创建一个用于计算(n^k) % m的方法：

int calc(int n, int k, int m)

那么当k = 15时，calc(n, 15, m)会递归地调用calc(n, 8, m)和calc(n, 7, m)。使用记忆化（memoization），结果的时间复杂度为_O(log k)_。

public static int calc(int n, long k) {
    if (n < 0 || k < 0)
        throw new IllegalArgumentException();
    if (n == 0)
        return 0;
    if (k == 0)
        return 1;
    return calc0(n, k, new HashMap<>());
}
private static int calc0(int n, long k, Map<Integer, Integer> cache) {
    Integer cachedValue = cache.get(k);
    if (cachedValue != null)
        return cachedValue;
    int result;
    if (k == 1)
        result = n % MODULO;
    else
        result = (int) ((long) calc0(n, k / 2, cache) * calc0(n, k - k / 2, cache) % MODULO);
    cache.put(k, result);
    return result;
}
private static final int MODULO = 10000007;

位运算解法

如果你不喜欢递归和记忆化，你可以使用位操作。实际上，这比递归方法稍微更有效率，有时使用更少的乘法和求余操作。

我不会对此进行解释。看看你是否能够弄清楚它是如何工作的。

public static int calc(int n, long k) {
    if (n < 0 || k < 0)
        throw new IllegalArgumentException();
    int e = n % MODULO;
    int r = ((k & 1) != 0 ? e : 1);
    for (long i = k >>> 1; i != 0; i >>>= 1) {
        e = (int) ((long) e * e % MODULO);
        if ((i & 1) != 0)
            r = (int) ((long) r * e % MODULO);
    }
    return r;
}
private static final int MODULO = 10000007;

测试

System.out.println(calc(282828,292929));
System.out.println(calc(123456789,987654321));
System.out.println(calc(Integer.MAX_VALUE, Long.MAX_VALUE));

输出

6154601
5111924
5910478

英文:

Both solutions below run in O(log k), unlike e.g. the code in the question (O(k)), and the answer by WJS using BigInteger. WJS's code starts getting slow when k is 6 digits. Both solutions below returns immediately even when k is Long.MAX_VALUE.

In the description in this answer, a^b means exponentiation, not bitwise xor.

You're on the right path using

(a * b) % c = ((a % c) * (b % c)) % c

What you're missing is

a ^ (b + c) = (a ^ b) * (a ^ c)

<h3>Recursive solution</h3>

Since the goal is to calculate (n^k) % (10^7 + 7), you can calculate this in O(log k) time by recursively splitting k.

E.g. if k = 15 then split like this

n^15  =  n^8 * n^7
      =  (n^4 * n^4) * (n^4 * n^3)
      =  ...

With modulo that means

(n^15) % m  =  ((n^8) % m * (n^7) % m) % m
            =  ...

If you create a method for calculating (n^k) % m

int calc(int n, int k, int m)

then with k = 15, calc(n, 15, m) calls calc(n, 8, m) and calc(n, 7, m) recursively. With memoization, the result has O(log k) time complexity.

public static int calc(int n, long k) {
	if (n &lt; 0 || k &lt; 0)
		throw new IllegalArgumentException();
	if (n == 0)
		return 0;
	if (k == 0)
		return 1;
	return calc0(n, k, new HashMap&lt;&gt;());
}
private static int calc0(int n, long k, Map&lt;Integer, Integer&gt; cache) {
	Integer cachedValue = cache.get(k);
	if (cachedValue != null)
		return cachedValue;
	int result;
	if (k == 1)
		result = n % MODULO;
	else
		result = (int) ((long) calc0(n, k / 2, cache) * calc0(n, k - k / 2, cache) % MODULO);
	cache.put(k, result);
	return result;
}
private static final int MODULO = 10000007;

<h3>Bitwise solution</h3>

If you don't like recursion and memoization, you can use bit manipulation. This is actually slightly more efficient than the recursive approach, sometimes using fewer multiplication and remainder operations.

I won't explain it. See if you can figure out how that works.

public static int calc(int n, long k) {
	if (n &lt; 0 || k &lt; 0)
		throw new IllegalArgumentException();
	int e = n % MODULO;
	int r = ((k &amp; 1) != 0 ? e : 1);
	for (long i = k &gt;&gt;&gt; 1; i != 0; i &gt;&gt;&gt;= 1) {
		e = (int) ((long) e * e % MODULO);
		if ((i &amp; 1) != 0)
			r = (int) ((long) r * e % MODULO);
	}
	return r;
}
private static final int MODULO = 10000007;

System.out.println(calc(282828,292929));
System.out.println(calc(123456789,987654321));
System.out.println(calc(Integer.MAX_VALUE, Long.MAX_VALUE));

Output

6154601
5111924
5910478

答案2

得分: 0

这是最简单的。您可以使用它来检查您的其他答案。

		System.out.println(fnc(282828,292929));
        System.out.println(yours(282828,292929));
	
	
	public static BigInteger fnc(int n, int k) {
		
		int modulo = (int) Math.pow(10, 7) + 7;
		BigInteger res = BigInteger.valueOf(n).pow(k)
				.mod(BigInteger.valueOf(modulo));
		return res;
	}

这是您的解决方案。您只需要使用long类型：

	public static long yours(long n, long k) {
		long res = 1;
		int modulo = (int) Math.pow(10, 7) + 7;
		// ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
        // 将 n % modulo 单独提取出来，因为 n 永远不会变化。
		long nmod = n % modulo;
		res = nmod % modulo;
		for (int i = 1; i < k; i++) {
			res = ((res % modulo) * (nmod)) % modulo;
		}
		return res;
	}

它们都打印出：

6154601
6154601

轻微的优化。

将n % modulo提取为nmod。只需计算一次。
由于第一次1 % modulo为1，只需将res初始化为nmod % modulo。然后只需迭代i < k次。

英文:

This is easiest. You can use it to check your other answers.

		System.out.println(fnc(282828,292929));
        System.out.println(yours(282828,292929));
	
	
	public static BigInteger fnc(int n, int k) {
		
		int modulo = (int) Math.pow(10, 7) + 7;
		BigInteger res = BigInteger.valueOf(n).pow(k)
				.mod(BigInteger.valueOf(modulo));
		return res;
	}

And here is your solution. You only needed to use long's

	public static long yours(long n, long k) {
		long res = 1;
		int modulo = (int) Math.pow(10, 7) + 7;
		// ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
        // pull out n % modulo since n never changes.
		long nmod = n% modulo;
		long res = nmod%modulo;
		for (int i = 1; i &lt; k; i++) {
			res = ((res% modulo)*(nmod))%modulo;
		}
		return res;
	}

They both print

6154601
6154601

Slight optimizations.

pull out n % modulo as nmod. Just compute once.
since 1 % modulo is 1 first time thru, just initialize res to nmod % modulo. Then just iterate to i < k times.

通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。

Find value of n^k modulo 10^7 + 7.

问题

答案1

递归解法

位运算解法

测试

答案2

如何根据 Java 中属性的值将对象列表转换为字符串列表？

如何从 Cosmos DB 中的现有表中访问分区键。

如何通过Java代码将CSV文件数据导入PostgreSQL表格？

如何在单一位置使用QAF定义适用于iOS和Android的平台特定页面元素？

如何在Playwright视觉比较中屏蔽多个定位器？

在C++中，可以使用可变模板参数来检索类型的内部类型。

selenium.common.exceptions.StaleElementReferenceException: Message: stale element reference: stale element not found

Creating and opening a URL to log in to Website via Basic Auth with Robot Framework/Selenium (Python)

AG Grid 在上下文菜单中以大文本形式打开

What's the correct way to type hint an empty list as a literal in python?

如何在Highcharts Gantt中更改本地化的星期名称

如何在同一个流中使用多个过滤器和映射函数？

如何使用Map/Set来将代码优化到O(n)？

.NET MAUI Android在GitHub Actions上构建失败，错误代码为1。