HackerRank Number Theory – Degree of an algebraic number – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: Degree of an algebraic number

Subdomeniu: Number Theory (number-theory)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464775195

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/degree-of-an-algebraic-number/problem

Cerinta

A number is *algebraic* if it is a root of some nonzero polynomial with integer coefficients. A number is *transcendental* if it is not algebraic.

For example, $11$, $i$, $\sqrt[3]{2}$ and $\phi$ ([golden ratio](http://en.wikipedia.org/wiki/Golden_ratio)) are algebraic, because they are roots of $x-11$, $x^2+1$, $x^3-2$ and $x^2-x-1$, respectively. Also, it can be shown that the sum and product of two algebraic numbers is also algebraic, so for example $24+i$, $\sqrt{2}+\sqrt{3}$ and $\sqrt[3]{11}\phi$ are also algebraic. However, it has been shown by Lindemann that [$\pi$ is transcendental](http://en.wikipedia.org/wiki/Lindemann%E2%80%93Weierstrass_theorem).

The *degree* of an algebraic number is the minimal degree of a polynomial with integer coefficients in which it is a root. For example, the degrees of $5$, $i$, $\sqrt[3]{2}$ and $\phi$ are $1$, $2$, $3$ and $2$, respectively.

Given $N$ positive integers $A_1$, $A_2$, ..., $A_N$, calculate the degree of the following algebraic number:
$$\sqrt{A_1} + \sqrt{A_2} + \sqrt{A_3} + \cdots + \sqrt{A_N}$$  

**Input Format**  
The first line of input contains $T$, the number of test cases. The descriptions of the test cases follow.

Each test case has two lines of input. The first line contains a single integer, $N$. The second line contains $N$ integers $A_1$, ..., $A_N$ separated by single spaces.

**Output Format**  
For each test case, output one line containing exactly one integer, which is the answer for that test case.

**Constraints**  
$1 \le T \le 10^5$  
$1 \le N \le 50$  
$1 \le A_i \le 10^7$  
The sum of the $N$'s in a single test file is at most $10^5$  

**Sample Input**  

    3
    1
    4
    3
    2 4 4
    4
    1 2 3 5

**Sample Output** 

    1
    2
    8

**Explanation**  
*Case 1*: A minimal polynomial of $\sqrt{4}$ is $2x-4$.  

*Case 2*: A minimal polynomial of $\sqrt{2}+\sqrt{4}+\sqrt{4}$ is $x^2-8x+14$.  

*Case 3*: A minimal polynomial of $\sqrt{1}+\sqrt{2}+\sqrt{3}+\sqrt{5}$ is:
$$x^8-8x^7-12x^6+184x^5-178x^4-664x^3+580x^2+744x-71$$

Cod sursa

# Enter your code here. Read input from STDIN. Print output to STDOUT
from itertools import *
import sys

def print_mat(A):
    print('\n'.join(''.join(map(str, row)) for row in A))

def e_sieve(n):
    '''generates primes <=n'''
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    falses = [False] * (n // 2)
    curr = 2
    while curr * curr <= n:
        sieve[curr * 2:: curr] = falses[:(n // curr) - 1]
        curr += 1
        while not sieve[curr]: curr += 1
    return [x for x in range(n) if sieve[x]]

primes = e_sieve(4000)

def factorize(n):
    '''returns a dictionary of prime factorization of n'''
    d = list()
    for p in primes:
        if p * p > n: break
        power = 0
        while n % p == 0:
            power += 1
            n //= p
        if power % 2 == 1:
            d.append(p)
        if n == 1: 
            break
    if n > 1: d.append(n)
    return d

def gauss_jordan(A, debug = False):
    n, m = len(A), len(A[0])
    pivot_row, pivot_col = 0, 0
    while pivot_row < n and pivot_col < m:
        i_max = None
        for i in range(pivot_row, n):
            if A[i][pivot_col] == 1:
                i_max = i
                break
        if i_max is None:
            pivot_col += 1
            continue
        else:
            if pivot_row != i_max:
                if debug: print("Swapping row %d and %d"%(pivot_row, i_max))
                A[pivot_row], A[i_max] = A[i_max], A[pivot_row]
                if debug: print_mat(A)
            for i in range(pivot_row + 1, n):
                if A[i][pivot_col] == 1:
                    if debug: print("Adding row %d to row %d"%(pivot_row, i))
                    for j in range(pivot_row, m):
                        A[i][j] ^= A[pivot_row][j]
                    if debug: print_mat(A)
            pivot_row += 1
            pivot_col += 1
    
def solve(A):
    A = [number for number in map(factorize, A) if number]
    if not A: return 0
    all_factors = set(x for number in A for x in number)
    prime_dict = {prime: rank for rank, prime in enumerate(all_factors)}
    matrix = [[0] * len(A) for _ in range(len(prime_dict))]
    for i, number in enumerate(A):
        for prime in number:
            matrix[prime_dict[prime]][i] = 1
    gauss_jordan(matrix)
    return sum(any(x > 0 for x in row) for row in matrix)

def all_matrices(n, m):
    for lists in product([0, 1], repeat = n * m):
        yield [list(lists[i * m: (i + 1) * m]) for i in range(n)]

T = int(sys.stdin.readline())
for caseno in range(T):
    N = int(sys.stdin.readline())
    A = map(int, sys.stdin.readline().split())
    print(2 ** solve(A))

HackerRank Number Theory – Degree of an algebraic number