Degree of an algebraic number

  • + 1 comment

    Python3 solution

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