두 자연수 N 과 P 를 가지고 다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자.
처음 출력하는 숫자는 N 이고, 두 번째 이후 출력하는 숫자들은 N 을 곱하고 P 로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N 에 을 N 을곱하고, 이 수를 P 로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N 을 곱하고 P 로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N 을 곱한 후 P 로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다.
예를 들어서, N=67,P=31 인 경우를 생각해보자.
즉 이 과정을 반복하면, 처음 67을 제외하면 3개의 숫자 25, 1, 5가 계속 무한히 반복되게 된다.
또 다른 예로, N=9 , P=3 을 가지고 시작하면, 9×9=81 이고 3 으로 나눈 나머지는 0 이며, 0×3 =0 이고 3 으로 나눈 나머지도 0 이기 때문에 처음 9 를 제외하면 0 이 무한히 반복되게 된다.
N 과 P 를 입력받아 위와 같이 정의된 연산을 수행하였을 때, 반복되는 부분에 포함된 서로 다른 숫자의 개수를 구하는 프로그램을 작성하시오.
입력 67 31 출력 3 입력 96 61 출력 60
출처:2012 지역 본선 초등 2/5