약수의 개수가 짝수인지 홀수인지 바로 알아내는 제곱수 판단하는 방법

1. 문제

 

11815번: 짝수? 홀수? (acmicpc.net)

11815번: 짝수? 홀수?

 

 

2. 풀이

 

소인수분해 해서 (지수+1)의 곱의 합으로 짝수인지 홀수인지 판단해볼라했는데 수가 10의 18제곱까지 있어서 그런지

 

시간초과

 

from sys import stdin

n = int(stdin.readline())

num_list = list(map(int,stdin.readline().split()))

for i in num_list:
    
    p = 2

    answer = 1

    count = 0

    while p*p <= i:
        
        while i % p == 0:
            
            i = i//p
            count += 1
            
        p += 1
        answer *= (count+1)
        count = 0
    
    if i > 1:
        
        answer *= 2

    if answer % 2 == 0:
        
        print(0,end = ' ')
    
    else:
        
        print(1, end = ' ')

 

 

정수론에서 제곱수의 약수의 개수는 홀수개이고, 그렇지 않은 수는 짝수개라는 사실이 있다

 

파이썬에서 제곱수를 판단하는 방법이 지금까지

 

int(i**(1/2)) 와 i**(1/2)가 같으면 되는걸로 알고 있었는데 틀렸다고 나오더라고

 

from sys import stdin

n = int(stdin.readline())

num_list = list(map(int,stdin.readline().split()))

for i in num_list:
    
    if int(i**(1/2)) == i**(1/2):
        
        print(1,end=' ')
    
    else:
        
        print(0,end=' ')

 

 

999999999999999999 이게 문제가 되더라

 

실제로 (1/2)제곱을 해보니까

 

 

1000000000를 제곱한다고 999999999999999999 나오는건아니잖아

 

실수오차 때문에 너무 큰 수에 대해 제곱근을 구하면 이런 문제가 생기더라

 

그래서... 제곱근을 판단할때 (1/2)제곱을 하고 나서 다시 제곱했을때 원래 수와 같은지를 판단하자

 

from sys import stdin

n = int(stdin.readline())

num_list = list(map(int,stdin.readline().split()))

answer = []

for i in num_list:
    
    if (int(i**(1/2))**2 == i):
        
        print(1,end=' ')
    
    else:
        
        print(0,end=' ')