[BOJ/백준] 9094 - 수학적 호기심 [python]

문제 링크

9094번: 수학적 호기심

문제 풀이

이 문제는 주어진 공식이 정수인 쌍의 갯수를 구하는 문제이다. 주어진 공식을 반복문을 통해 계속 계산하다보면, 계산에 대한 시간이 매우 커져 시간초과가 발생한다. 따라서, a^2+b^2의 값을 미리 계산해놓은 뒤, 테스트케이스가 들어올 때마다 미리 계산된 값에 m을 더해주는 방식으로 계산을 줄일 수 있다.

정답 코드

memory = [[0] * 101 for _ in range(101)]
for b in range(2, 101) :
    for a in range(1, b) :
        memory[b][a] = a ** 2 + b ** 2
for _ in range(int(input())) :
    n, m = map(int, input().split())
    cnt = 0
    for b in range(2, n) :
        for a in range(1, b) :
            if (memory[b][a] + m) % (a * b) == 0 : cnt += 1
    print(cnt)