Soluție HackerRank pentru Degree of an algebraic number, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor…
- Problemă: Degree of an algebraic number
- Domeniu: Number Theory
- Limbaj: Python 3
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
Cerință
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} + ·s + 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 ≤ T ≤ 10^5
1 ≤ N ≤ 50
1 ≤ A_i ≤ 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 sursă
# 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))