TopCoder SRM 567 Div1

2013. 01. 21.

첫 Div1.. 다행히 블루는 사수 성공! ㅋㅋ 레이팅이 +20되었다.

정말 입실론만큼 레이팅이 올랐다..

소인수분해 짤때 실수만 안했어도 더 올랐을텐데! ㅋㅋㅋ

250 - 그냥 수학 문제였다.

(sqrt(a)+sqrt(b))^2가 정수가 되는 (a,b) 순서쌍(ordered pair)의 개수를 구해라!

단, 여기서 1≤a≤N이고 1≤b≤M이다 (a, b는 77,777 보다 작거나 같은 자연수).

저 식을 전개해보면 알 수 있듯이, 이 식은 루트a * 루트b가 정수가 되어야만 식 전체가 정수가 된다.

자, 여기서 잠시 고민해보면, 소인수분해를 사용하면 되리란걸 알 수 있다.

1 ~ N (혹은 M) 을 돌면서 각 숫자들을 소인수분해 한 뒤,

소인수들중에 홀수번 등장하는 인수들을 곱한 수를 L이라 하면,

이제 L에다가 1부터 모든 제곱수(이 수를 S라 하자)를 곱해가며

M보다 작거나 같은 L*S들의 개수를 세면

이 개수가 바로 답이다.

500

1000