Tuesday, May 27, 2014

2005년도 KOI 지역본선 고등부 5번

Problem Link

자연수 N의 양의 배수 집합을 S라 할 때, S의 원소 중 각 자릿수를 이루는 숫자의 종류가 가장 적은 수의 집합을 T라 하고, T의 원소 중 최솟값을 구하는 문제를 풀었는데...
T에서 숫자의 종류가 항상 2이하가 되는 것 같다.

만약, N이 2나 5의 배수가 아니라면 S에서의 숫자의 종류는 항상 1개이다.
1,11,111, 111111 같이 1들로 이루어진 수들은 무한개이므로 이 수들 중 N으로 나눈 나머지가 같은 두 수가 항상 존재한다. 그 두 수의 차이는 11111....* 10^k이고 N으로 나누어떨어진다. 즉 11111 .... *10^k = Q(몫)*N이고 N은 10의 배수가 아니므로 11111....은 N으로 나누어떨어진다. N이 2나 5의 배수라도 앞서 말한 10^k을 나누고 곱함으로써 연속된 숫자들로 나타날 수 있게 만들 수 있고, 그 뒤에 임의의 개수의 0을 붙여서 N으로 나누어떨어지게 할 수 있다. 따라서 모든 수의 T에서 숫자의 종류는 1개 또는 2개이다. 몇 가지를 생략하고 적어놓아서 엄밀하지않아 보이지만 뭐...ㅋㅋㅋ 이와 비슷한 문제를 접하면 이런 쪽으로 생각하면 되겠다.

Source Code

No comments:

Post a Comment