(C++) 백준 2526 - 싸이클

https://www.acmicpc.net/problem/2526

문제

> 처음 출력수는 N, 두번 째는 N을 곱하고 P로 나눈 나머지이다. 이 계산을 반복하다보면 반복되는 부분이 생긴다.
> 따라서 반복되는 부분에 포함된 수의 개수를 구해라.
> 예) N = 67, P = 31일때 1 = 67, 2 = 25, 3 = 1, 4 = 5, 5 = 25이다. 즉 25, 1, 5가 반복되므로 3을 출력한다.

접근

벡터에 문제에 주어진연산을 해 나온 값을 인덱스로 하여 반복문을 통해 값을 넣는다. 반복문을 돌다 값이 이미 들어있으면 거기까지의 개수를 구하고 출력한다.

문제해결

> 첫사이클은 N이고 계산식에 포함되지 않기 때문에 2부터 반복문을 돌려준다.
> tmp값은 연산하면서 계속 변화하기 때문에 갱신해주며 문제의 수식에 넣어 연산한다.
> 만약 연산결과를 인덱스로하는 벡터 값이 이미 있다면 현재 i와 그 인덱스의 값에 있는 i의 차를 구해 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, P;
	cin >> N >> P;
	int tmp = N;

	vector<int> cycle(P,0);
	for (int i = 2; ; i++)
	{
		int key = tmp * N % P;
		if (cycle[key] != 0)
		{
			cout << i - cycle[key] << '\n';
			break;
		}
		cycle[key] = i;
		tmp = key;
	}
}

후기

문제에서 예시가 오류가있어 이해가 어려웠지만 예제를 넣고해서 맞췄다.