o（log n）解决方案的方法和代码 [英] Approach and Code for o(log n) solution
问题描述
我想计算（ f（N）mod M ）。
这些就是约束。
- 1≤N≤10 ^ 9
- 1≤M≤10 ^ 3
这是我的代码
test = int（input（））
ans = 0
对于范围（test）中的情况：
arr = [int（x）for input in x（ ）.split（）]
N = arr [0]
mod = arr [1]
＃ret = sum（[y中的y（y ** y） range（N + 1）]）
＃ans = ret
对于range（1，N + 1）中的i：
ans =（ans + pow（i，i ，mod））％mod
打印（ans）
我尝试了另一种方法，但徒劳。
这是该代码
从functools导入reduce
test = int（input（））
answer = 0
对于范围（测试）中的情况：
arr = [int（x）for input（）。split（）中的x]
N = arr [0]
mod = arr [1]
答案= reduce（lambda K，N：x + pow（N，N），range（1，N + 1））％M
print（answer）
两个建议：
-
让
0 ^ 0 = 1成为您的使用方式。这似乎是我如何处理该问题的最佳指导。 -
计算
k ^ k -
进行一次初始遍历，其中所有
k（不是指数） ）更改为k mod M，然后再执行其他操作。 -
在计算
（k mod M）^ k ，如果中间结果是您已经访问过的结果，则可以减少迭代次数以继续进行，直到最多再增加一个循环。
示例：令N = 5且M =3。我们要计算0 ^ 0 + 1 ^ 1 + 2 ^ 2 + 3 ^ 3 + 4 ^ 4 + 5 ^ 5（mod 3）。
首先，我们应用建议3。现在我们要计算0 ^ 0 + 1 ^ 1 + 2 ^ 2 + 0 ^ 3 + 1 ^ 4 + 2 ^ 5（mod 3）。
接下来，我们开始评估并立即使用建议1来获得1 + 1 + 2 ^ 2 + 0 ^ 3 + 1 ^ 4 + 2 ^ 5（mod 3）。 2 ^ 2是4 = 1（mod 3），我们做一个记号（2 ^ 2 = 1（mod 3））。接下来，我们发现0 ^ 1 = 0，0 ^ 2 = 0，所以我们有一个大小为1的循环，这意味着不需要进一步的乘法就可以确定0 ^ 3 = 0（mod 3）。注意事项。 1 ^ 4的过程类似（我们在第二次迭代中告诉我们，循环的大小为1，因此1 ^ 4为1，请注意）。最后，我们得到2 ^ 1 = 2（mod 3），2 ^ 2 = 1（mod 3），2 ^ 3 = 2（mod 3），一个长度为2的循环，因此我们可以跳过前面的偶数2 ^ 5并且无需再次检查就知道2 ^ 5 = 2（mod 3）。
我们的总和现在是1 + 1 + 1 + 0 + 1 + 2 （mod 3）= 2 +1 + 0 + 1 + 2（mod 3）= 0 + 0 +1 + 2（mod 3）= 0 +1 + 2（mod 3）= 1 + 2（mod 3）= 0 （mod 3）。
这些规则将对您有所帮助，因为您的案例看到N比M大得多。如果相反，则-如果N比M小得多-您不会从我的方法中受益（并且使用模数wrt M对结果的影响较小）。
伪代码：
Compute（N，M）
1. sum = 0
2. i = 0至N时
3. term = SelfPower（i，M）
4. sum =（sum + term）％M
5. return sum
SelfPower（k，M）
1. selfPower = 1
2.迭代=新的HashTable
3.对于i = 1到k做
4. selfPower =（selfPower *（k％M））％M
5。如果迭代[s elfPower]定义为
6. i = k-（k-i）％（i-迭代[selfPower]）
7.清除迭代
8. else迭代[selfPower] = i
9. return selfPower
示例执行：
resul = Compute（5，3）
sum = 0
i = 0 0
term = SelfPower（0，3）
selfPower = 1
迭代次数= []
//不进入循环
返回1
总和=（0 + 1）％3 = 1
i = 1
项= SelfPower（1，3）
selfPower = 1
迭代次数= []
i = 1
selfPower =（1 * 1％3）％3 = 1
迭代[1]未定义
迭代[1] = 1
返回1
总和=（1 + 1）％3 = 2
i = 2
项= SelfPower（2，3）
selfPower = 1
迭代次数= []
i = 1
selfPower =（1 * 2％3）％3 = 2
次迭代[2]未定义
次迭代[2] = 1
i = 2
selfPower =（2 * 2％3）％3 = 1
迭代[1]未定义
迭代[1] = 2
返回1
总和=（2 + 1） ％3 = 0
i = 3
项= SelfPower（3，3）
selfPower = 1
迭代次数= []
i = 1
selfPower =（ 1 * 3％0）％3 = 0
迭代[0]未定义
迭代[0] = 1
i = 2
selfPower =（0 * 3％0） ％3 = 0
次迭代[0]定义为1
i = 3-（3-2）％（2-1-3）= 3
次迭代为空
返回0
sum =（0 + 0）％3 = 0
i = 4
项= SelfPower（4，3 ）
selfPower = 1
次迭代= []
i = 1
selfPower =（1 * 4％3）％3 = 1
次迭代[1]未定义
次迭代[1] = 1
i = 2
selfPower =（1 * 4％3）％3 = 1
次迭代[1]定义为1
i = 4-（4-2）％（2-1）= 4
迭代为空白
返回1
总和=（0 + 1）％3 = 1
i = 5
项= SelfPower（5，3）
selfPower = 1
迭代次数= []
i = 1
selfPower =（1 * 5％3）％3 = 2 $未定义b $ b迭代[2]
迭代[2] = 1
i = 2
selfPower =（2 * 5％3）％3 = 1
迭代[1 ]未定义
次迭代[1] = 2
i = 3
selfPower =（1 * 5％3）％3 = 2
迭代次数[2]定义为1
i = 5-（5-3）％（3-1）= 5
迭代为空白
返回2
总和=（1 + 2）％3 = 0
返回0
f(N) = 0^0 + 1^1 + 2^2 + 3^3 + 4^4 + ... + N^N.
I want to calculate (f(N) mod M).
These are the constraints.
- 1 ≤ N ≤ 10^9
- 1 ≤ M ≤ 10^3
Here is my code
test=int(input())
ans = 0
for cases in range(test):
arr=[int(x) for x in input().split()]
N=arr[0]
mod=arr[1]
#ret=sum([int(y**y) for y in range(N+1)])
#ans=ret
for i in range(1,N+1):
ans = (ans + pow(i,i,mod))%mod
print (ans)
I tried another approach but in vain. Here is code for that
from functools import reduce
test=int(input())
answer=0
for cases in range(test):
arr=[int(x) for x in input().split()]
N=arr[0]
mod=arr[1]
answer = reduce(lambda K,N: x+pow(N,N), range(1,N+1)) % M
print(answer)
Two suggestions:
Let
0^0 = 1be what you use. This seems like the best guidance I have for how to handle that.Compute
k^kby multiplying and taking the modulus as you go.Do an initial pass where all
k(not exponents) are changed tok mod Mbefore doing anything else.While computing
(k mod M)^k, if an intermediate result is one you've already visited, you can cut back on the number of iterations to continue by all but up to one additional cycle.
Example: let N = 5 and M = 3. We want to calculate 0^0 + 1^1 + 2^2 + 3^3 + 4^4 + 5^5 (mod 3).
First, we apply suggestion 3. Now we want to calculate 0^0 + 1^1 + 2^2 + 0^3 + 1^4 + 2^5 (mod 3).
Next, we begin evaluating and use suggestion 1 immediately to get 1 + 1 + 2^2 + 0^3 + 1^4 + 2^5 (mod 3). 2^2 is 4 = 1 (mod 3) of which we make a note (2^2 = 1 (mod 3)). Next, we find 0^1 = 0, 0^2 = 0 so we have a cycle of size 1 meaning no further multiplication is needed to tell 0^3 = 0 (mod 3). Note taken. Similar process for 1^4 (we tell on the second iteration that we have a cycle of size 1, so 1^4 is 1, which we note). Finally, we get 2^1 = 2 (mod 3), 2^2 = 1(mod 3), 2^3 = 2(mod 3), a cycle of length 2, so we can skip ahead an even number which exhausts 2^5 and without checking again we know that 2^5 = 2 (mod 3).
Our sum is now 1 + 1 + 1 + 0 + 1 + 2 (mod 3) = 2 + 1 + 0 + 1 + 2 (mod 3) = 0 + 0 + 1 + 2 (mod 3) = 0 + 1 + 2 (mod 3) = 1 + 2 (mod 3) = 0 (mod 3).
These rules will be helpful to you since your cases see N much larger than M. If this were reversed - if N were much smaller than M - you'd get no benefit from my method (and taking the modulus w.r.t. M would affect the outcome less).
Pseudocode:
Compute(N, M)
1. sum = 0
2. for i = 0 to N do
3. term = SelfPower(i, M)
4. sum = (sum + term) % M
5. return sum
SelfPower(k, M)
1. selfPower = 1
2. iterations = new HashTable
3. for i = 1 to k do
4. selfPower = (selfPower * (k % M)) % M
5. if iterations[selfPower] is defined
6. i = k - (k - i) % (i - iterations[selfPower])
7. clear out iterations
8. else iterations[selfPower] = i
9. return selfPower
Example execution:
resul = Compute(5, 3)
sum = 0
i = 0
term = SelfPower(0, 3)
selfPower = 1
iterations = []
// does not enter loop
return 1
sum = (0 + 1) % 3 = 1
i = 1
term = SelfPower(1, 3)
selfPower = 1
iterations = []
i = 1
selfPower = (1 * 1 % 3) % 3 = 1
iterations[1] is not defined
iterations[1] = 1
return 1
sum = (1 + 1) % 3 = 2
i = 2
term = SelfPower(2, 3)
selfPower = 1
iterations = []
i = 1
selfPower = (1 * 2 % 3) % 3 = 2
iterations[2] is not defined
iterations[2] = 1
i = 2
selfPower = (2 * 2 % 3) % 3 = 1
iterations[1] is not defined
iterations[1] = 2
return 1
sum = (2 + 1) % 3 = 0
i = 3
term = SelfPower(3, 3)
selfPower = 1
iterations = []
i = 1
selfPower = (1 * 3 % 0) % 3 = 0
iterations[0] is not defined
iterations[0] = 1
i = 2
selfPower = (0 * 3 % 0) % 3 = 0
iterations[0] is defined as 1
i = 3 - (3 - 2) % (2 - 1) = 3
iterations is blank
return 0
sum = (0 + 0) % 3 = 0
i = 4
term = SelfPower(4, 3)
selfPower = 1
iterations = []
i = 1
selfPower = (1 * 4 % 3) % 3 = 1
iterations[1] is not defined
iterations[1] = 1
i = 2
selfPower = (1 * 4 % 3) % 3 = 1
iterations[1] is defined as 1
i = 4 - (4 - 2) % (2 - 1) = 4
iterations is blank
return 1
sum = (0 + 1) % 3 = 1
i = 5
term = SelfPower(5, 3)
selfPower = 1
iterations = []
i = 1
selfPower = (1 * 5 % 3) % 3 = 2
iterations[2] is not defined
iterations[2] = 1
i = 2
selfPower = (2 * 5 % 3) % 3 = 1
iterations[1] is not defined
iterations[1] = 2
i = 3
selfPower = (1 * 5 % 3) % 3 = 2
iterations[2] is defined as 1
i = 5 - (5 - 3) % (3 - 1) = 5
iterations is blank
return 2
sum = (1 + 2) % 3 = 0
return 0
这篇关于o（log n）解决方案的方法和代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
