Soluție HackerRank pentru Devu Vs Police, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Devu Vs Police
- Domeniu: Number Theory
- Limbaj: Python 3
Challenge: Devu Vs Police
Subdomeniu: Number Theory (number-theory)
Scor cont: 60.0 / 60
Submission status: Accepted
Submission score: 1.0
Submission ID: 464744631
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/devu-police/problem
Cerință
It is holi festival, festival of colors. Devu is having fun playing holi and is throwing balloons with his girlfriend Glynis. Police saw this mischief and tried arresting his girlfriend, Devu being a mathematician asked police not to arrest his girlfriend and instead torture him with brain teaser. Devu was a young engineering fellow and he did not knew that policeman was equally good in mathematics, policeman gave Devu a problem which is as follows:
Let f(n,k) = n^k
Your aim is to answer f(n_1,k_1)^f(n_2,k_2) bmod n
Can you help devu and his girlfriend rescue from modern police.
Input Format
You are given T which is the number of queries to solve.
Each Query consist of 5 space separated integers n_1,k_1,n_2,k_2,n
Output Format
Output contains exactly T lines. i^{text{th}} line containing the answer for the i^{text{th}} query.
Constraints
- 1 ≤ T ≤ 10^4
- 0 ≤ n_1,k_1,n_2,k_2 ≤ 10^9
- 1 ≤ n ≤ 10^7
Note The output to 0^0 should be 1.
Cod sursă
lim = 3200
mark = bytearray(lim)
primes = [2]
for i in range(3, lim, 2):
if mark[i]: continue
primes.append(i)
for j in range(3 * i, lim, 2 * i):
mark[j] = 1
def factor(n):
f = {}
for p in primes:
if p * p > n: break
while n % p == 0:
n //= p
f[p] = f.get(p, 0) + 1
if n > 1: f[n] = 1
return f
T = int(input())
for t in range(T):
n1, k1, n2, k2, n = map(int, input().split())
if n1 == 0:
f1 = 1 if k1 == 0 else 0
else:
f1 = pow(n1, k1, n) or n
if n2 == 0:
f2 = 1 if k2 == 0 else 0
else:
phi = 1
for p, e in factor(n).items():
phi *= (p - 1) * p ** (e - 1)
f2 = pow(n2, k2, phi) or phi
print(pow(f1, f2, n))