Approach and code for solving o (log n)
f (N) = 0 ^ 0 + 1 ^ 1 + 2 ^ 2 + 3 ^ 3 + 4 ^ 4 + ... + N ^ N.
I want to calculate ( f (N) mod M ).
These are limitations.
- 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 a different approach, but in vain. Here is the 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)
source to share
Two suggestions:
-
Let it
0^0 = 1
be what you use. This seems like the best guide I have for how to deal with this. -
Calculate
k^k
by multiplying and taking the modulus as you go. -
Make an initial pass where everyone
k
(non-exponents) change tok mod M
before doing anything else. -
When calculating
(k mod M)^k
, if the intermediate result is one that you have already visited, you can reduce the number of iterations to continue everything, but to one additional loop.
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 Proposition 3. Now we want to calculate 0 ^ 0 + 1 ^ 1 + 2 ^ 2 + 0 ^ 3 + 1 ^ 4 + 2 ^ 5 (mod 3).
We then start evaluating and using sentence 1 first to get 1 + 1 + 2 ^ 2 + 0 ^ 3 + 1 ^ 4 + 2 ^ 5 (mod 3). 2 ^ 2 - 4 = 1 (mod 3), from which we make the note (2 ^ 2 = 1 (mod 3)). Next we find 0 ^ 1 = 0, 0 ^ 2 = 0, so we have a loop of size 1, which means that no further multiplication is required to calculate 0 ^ 3 = 0 (mod 3). Note accepted. Similar process for 1 ^ 4 (we say in the second iteration that we have a loop 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 an even number that exhausts 2 ^ 5 and without checking again, we know that 2 ^ 5 = 2 (mod 3).
Our sum is 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 a lot more than M. If it were the opposite - if N was much less than M - you would not get any benefit from my method (and taking the module at address M influence the result 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
Execution example:
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
source to share