9094번: 수학적 호기심

9094번: 수학적 호기심 (acmicpc.net)

9094번: 수학적 호기심

(a,b)=(1,2) ,(1,3) ,(1,4) ,(1,5) ,,,,,,(1,n-1)

(a,b)=(2,3) ,(2,4) ,(2,5), (2,6) ,,,,,,(2,n-1)

(a,b)=(3,4), (3,5), (3,6), (3,7) ,,,,,,(3,n-1)

. . .

(a,b)=(n-2,n-1)

>>

식이 정수인 것을 판단하는 기준은 분자를 분모로 나누었을 때 나머지가 0인 숫자쌍으로 한다.

python3 에서는 시간초과고 pypy3에서는 정답인데 왜 그런지는 알아봐야할 것 같다.

python3 에서는 input() 함수가 시간 초과의 원인인 것 같다.

시간 초과를 없애려면 sys.stdin.readline() 를 사용하면 시간을 줄일 수 있다.

 

T=int(input())

for k in range(0,T):
    n,m=map(int, input().split())
    cnt=0

    for i in range(1,n+1):
        for j in range(i+1,n):
            a=i
            b=j
            if (a**2+b**2+m)%(a*b)==0:
                cnt+=1

    print(cnt)