[알고리즘 문제] 잊어버린 비밀번호 (Python / 파이썬)

문제

지니는 알고리즘 사이트의 비밀번호 마지막 숫자 부분을 까먹어서 비상이다.
맞힐 수 있는 확률은 10분의1이지만 다시 한번만 틀리게 된다면 비밀번호를 바꿔야 하기 때문에 쪽지에 메모했던 힌트를 꺼냈다. 마지막 숫자의 값은 ‘A의 제곱은 B의 제곱보다 N만큼 크다’를 만족하는 자연수 (A, B)쌍의 수다. 지니의 비밀번호 마지막 자리 숫자를 구해주자.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N이 주어진다.
( 1 ≤ T ≤ 10, 1 ≤ N ≤ 1,000 ) 

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 유니의 비밀번호 마지막 자리를 출력한다.

---

문제 풀이

A의 제곱은 B의 제곱보다 N만큼 크다를 만족하는 자연수 (A, B)의 쌍이 몇개인지 찾는 문제 입니다.

위의 문장을 식으로 표현하면 A * A - B * B = N 입니다. 

 

따라서, A가 될 수 있는 수와 B가 될 수 있는 수를 반복문을 통해 하나씩 확인하며

식을 만족하는지 확인해주면 됩니다. 

이때, 위의 식은 음수가 나올 수 없으므로 B의 범위를 A보다 작을 때까지로 설정해줘야 합니다.

 

식을 만족할 때마다 개수를 세어주면 (A, B) 쌍의 개수를 구할 수 있습니다.

---

My Code

for tc in range(int(input())):
    n = int(input()) 

    count = 0
    for i in range(1, 1001): # A의 범위
        for j in range(1, i): # B의 범위
            if i * i - j * j == n: # 식을 만족하면
                count += 1         # 개수를 세어줌 

    print('#' + str(tc + 1), end = ' ')
    print(count)