We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
# Enter your code here. Read input from STDIN. Print output to STDOUTfromitertoolsimport*importsysdefprint_mat(A):print('\n'.join(''.join(map(str,row))forrowinA))defe_sieve(n):'''generatesprimes<=n'''sieve=[True]*(n+1)sieve[0]=sieve[1]=Falsefalses=[False]*(n// 2)curr=2whilecurr*curr<=n:sieve[curr*2::curr]=falses[:(n// curr) - 1]curr+=1whilenotsieve[curr]:curr+=1return[xforxinrange(n)ifsieve[x]]primes=e_sieve(4000)deffactorize(n):'''returnsadictionaryofprimefactorizationofn'''d=list()forpinprimes:ifp*p>n:breakpower=0whilen%p==0:power+=1n//= pifpower%2==1:d.append(p)ifn==1:breakifn>1:d.append(n)returnddefgauss_jordan(A,debug=False):n,m=len(A),len(A[0])pivot_row,pivot_col=0,0whilepivot_row<nandpivot_col<m:i_max=Noneforiinrange(pivot_row,n):ifA[i][pivot_col]==1:i_max=ibreakifi_maxisNone:pivot_col+=1continueelse:ifpivot_row!=i_max:ifdebug:print("Swapping row %d and %d"%(pivot_row,i_max))A[pivot_row],A[i_max]=A[i_max],A[pivot_row]ifdebug:print_mat(A)foriinrange(pivot_row+1,n):ifA[i][pivot_col]==1:ifdebug:print("Adding row %d to row %d"%(pivot_row,i))forjinrange(pivot_row,m):A[i][j]^=A[pivot_row][j]ifdebug:print_mat(A)pivot_row+=1pivot_col+=1defsolve(A):A=[numberfornumberinmap(factorize,A)ifnumber]ifnotA:return0all_factors=set(xfornumberinAforxinnumber)prime_dict={prime:rankforrank,primeinenumerate(all_factors)}matrix=[[0]*len(A)for_inrange(len(prime_dict))]fori,numberinenumerate(A):forprimeinnumber:matrix[prime_dict[prime]][i]=1gauss_jordan(matrix)returnsum(any(x>0forxinrow)forrowinmatrix)defall_matrices(n,m):forlistsinproduct([0,1],repeat=n*m):yield[list(lists[i*m:(i+1)*m])foriinrange(n)]T=int(sys.stdin.readline())forcasenoinrange(T):N=int(sys.stdin.readline())A=map(int,sys.stdin.readline().split())print(2**solve(A))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Degree of an algebraic number
You are viewing a single comment's thread. Return to all comments →
Python3 solution