Thursday, August 29, 2013

Asia Regional Contest 2012 in Tokyo A

http://www.acmicpc.net/problem/3825

<Description>
은행수란 정수 m과 n의 쌍 (m,n)이다. 예를 들어, (1,1), (-2,1), (-3,-1)은 은행수이다.
은행수의 곱셈 (m,n) · (x,y) = (mx - ny, my + nx) 이다. 예를 들어, (1,1)·(-2,1) = (-3,-1)이다.
이 때, (m,n) · (x,y) = (p,q)를 만족하는 은행수 (x,y)가 존재한다면, (m,n)은 은행수 (p,q)의 약수라고 한다. 모든 (1,0), (0,1), (-1,0), (0,-1), (m,n), (-n,m), (-m,-n), (n,-m)은 임의의 은행수 (m,n)의 약수이다. 만약, m2 + n2 > 1이라면, 앞의 8개 수는 모두 다를 것이다. 즉, m2 + n2 > 1을 만족하는 은행수는 적어도 8개의 약수가 있다. 만약, m2 + n2 > 1을 만족하는 은행수 (m,n)의 약수가 8개라면, 이 수를 소수라고 한다.
은행수가 주어졌을 때, 소수인지 아닌지 알아내는 문제이다.
---------------------------------------------------------------------------------------------------------------
문제를 처음 접하게 되면 생소한 정의에 낯설게 느껴지는데 input data limit를 보고 희망을 가지게 된다. 1 < m2 + n2 < 20000.
 
문제의 정의에 의해 (m,n) · (x,y) = (p,q)라면, (m2 + n2)(x2 + y2) = p2 + q2 가 된다는 것까지는 쉽게 알 수 있지만 별 의미가 없다.  m2 + n2 > 0인 경우에  m2 + n2이 mp + nq와 mq - np의 공약수라면 (m,n)은 (p,q)의 약수이고, 그 역도 성립한다는 사실 하나만으로도 이 문제는 쉽게 풀린다.
그런데 저 정리를 증명을 못했는데 고민해 볼 만한 것 같다.

No comments:

Post a Comment