[백준 2526] 싸이클

문제출처: https://www.acmicpc.net/problem/2526

문제

두 자연수 N과 P를 가지고  다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는  숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다. 

예를 들어서, N=67, P=31인 경우를 생각해보자. 처음 출력되는 숫자는 67이고, 두 번째로 출력되는 숫자는 67*67 = 4489를 31로 나눈 나머지 25이다. 다음에는 25*67 = 1675를 31로 나눈 나머지 1, 다음에는 1*67 = 67을 31로 나눈 나머지 5가 차례대로 출력된다. 다음에는 5*67 = 335를 31로 나눈 나머지 25가 출력되는데, 이 수는 이미 이전에 출력된 수이다. 이 과정을 그림으로 보이면 다음과 같다.

즉 이 과정을 반복하면, 처음 67을 제외하면 3개의 숫자 25, 1, 5가 계속 무한히 반복되게 된다.   또 다른 예로, N=9, P=3을 가지고 시작하면, 9*9 = 81이고 3으로 나눈 나머지는 0이며, 0*3 = 0이고 3으로 나눈 나머지도 0이기 때문에 처음 9를 제외하면 0이 무한히 반복되게 된다. 

N과 P를 입력받아 위와 같이 정의된 연산을 수행하였을 때,  반복되는 부분에 포함된 서로 다른 숫자의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 처음 시작하는  N과 P가 공백을 사이에 두고 주어진다. 단, 1<=N<=1,000, 2<=P<=97이다.  

출력

첫째 줄에 반복되는 부분에 포함된 서로 다른 숫자의 개수를 출력한다.

풀이

언제나 그렇듯 문제만 잘 이해하면 쉬운문제입니다. 

구현 할 때 문제를 잘 이해해봅시다. 숫자가 계속 순환하면서 싸이클을 이룰 때, 어떤특징을 가질까요? 싸이클의 개수를 구하는문제이므로 순환되는 수의 횟수를 담은 배열선언까지는 많은 분들이 할 수 있을것이고, 그러고나서 중요한 것은 숫자를 세다가 2번세는 경우가 나올 때 연산을 마치는것입니다. 예를들어 25->1->5일때 5다음에 25가 나올때 셈횟수가2가되는데 그렇다면 또 다시 같은 p로 나누기 때문에 25->1->5로 계속 무한히 반복할게 자명하기때문입니다.(생각을 잘해보세요.) 이런 아이디어만 구현할줄 알면됩니다. 마지막으로,순환되는 수는 0~p-1까지이므로 15행처럼 0부터 p전까지만 확인하면됩니다.   

코드

#include<iostream>
#include<vector>
using namespace std;
int check[1001];
void func(int x);
int n, p;
int main()
{
	cin >> n >> p;
	int cnt = 0;
	//계산함수
	func(n);

	//check[]가 2인 갯수 출력
	for (int i = 0; i <p; i++)
	{
		if (check[i] == 2)cnt++;
	}
	cout << cnt << endl;
}
void func(int x)
{
	//한번 나온값이 또 나오면?
	//또 나올 떄 까지의 과정들이 싸이클임
	if (check[x] == 2)return;
	check[x]++;
	func(x * n % p);
}

결과