HackerRank Number Theory – Devu Vs Police

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

Cerinta

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 \le T \le 10^4$       
- $0 \le n_1,k_1,n_2,k_2 \le 10^9 $       
- $1 \le n \le 10^7 $

**Note** The output to $0^0$ should be $1$.

Cod sursa

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))