HackerRank Number Theory – Primitive Problem

Challenge: Primitive Problem

Subdomeniu: Number Theory (number-theory)

Scor cont: 20.0 / 20

Submission status: Accepted

Submission score: 1.0

Submission ID: 464721731

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/primitive-problem/problem

Cerinta

We define a *primitive root* of prime number $p$ to be some integer $g \in [1, p-1]$ satisfying the property that all values of $g^x \bmod p$ where $x \in [0, p - 2]$ are different. 

For example: if $p = 7$, we want to look at all values of $g$ in the inclusive range from $1$ to $p - 1 = 6$. For $g = 3$, the powers of $g^x \bmod p$ (where $x$ is in the inclusive range from $0$ to $p - 2 = 5$) are as follows:

- $3^0=1 \pmod 7$  
- $3^1=3 \pmod 7$  
- $3^2=2 \pmod 7$  
- $3^3=6 \pmod 7$  
- $3^4=4 \pmod 7$  
- $3^5=5 \pmod 7$

Note that each of these evaluates to one of the six distinct integers in the range $[1, p-1]$.

Given prime $p$, find and print the following values as two space-separated integers on a new line:

1. The smallest primitive root of prime $p$.
2. The total number of primitive roots of prime $p$.  

**Need Help?** Check out a breakdown of this process at [Math Stack Exchange](http://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number).

Input Format

A single prime integer denoting $p$.

Output Format

Print two space-separated integers on a new line, where the first value is the smallest primitive root of $p$ and the second value is the total number of primitive roots of $p$.

Constraints

+ $2 < p < 10^9$

Cod sursa

import math

def modexp_lr(a, b, n):
    r = 1
    for bit in reversed(bits_of_n(b)):
        r = r * r % n
        if bit == 1:
            r = r * a % n
    return r

def bits_of_n(n):
    bits = []
    while n:
        bits.append(n % 2)
        n //= 2
    return bits

def p_factors(num, num_c, p_to_test, prime_factors):
    while num_c % 2 == 0:
        num_c //= 2
        if 2 in prime_factors:
            prime_factors[2] += 1
        else:
            prime_factors[2] = 1
    for x in range(3, int(math.sqrt(num_c)) + 1, 2):
        while num_c % x == 0:
            if x in prime_factors:
                prime_factors[x] += 1
            else:
                prime_factors[x] = 1
            num_c //= x
    if num_c > 2:
        prime_factors[num_c] = 1
    p_to_test = [(num - 1) // x for x in prime_factors]
    return p_to_test, prime_factors

def main():
    num = int(input())
    num_c = num - 1
    p_to_test = []
    prime_factors = {}
    p_to_test, prime_factors = p_factors(num, num_c, p_to_test, prime_factors)
    num_of_p_roots = 1
    for key, value in prime_factors.items():
        num_of_p_roots *= (((key ** value) // key) * ((key - 1)))
    for x in range(2, num):
        flag = 0
        for y in p_to_test:
            if modexp_lr(x, y, num) != 1:
                flag += 1
        if flag == len(p_to_test):
            print(x, num_of_p_roots)
            break

main()