나머지 수열의 순환 길이
면접 대비시간 제한1초메모리 제한128 MB
N과 P가 주어질 때 a_{i+1} = a_i*N mod P 수열을 시뮬레이션해서 반복되는 주기의 길이를 구합니다.
문제
두 자연수 N과 P가 주어진다. 수열 a_0, a_1, a_2, ...를 다음과 같이 만든다.
a_0 = Ni >= 0일 때,a_{i+1}은a_i * N을P로 나눈 나머지이다.
이 과정을 계속하면 이전에 나온 값이 다시 나타나고, 그때부터 같은 값들이 같은 순서로 반복된다. 반복되는 부분에 포함된 서로 다른 수의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 처음 시작하는 두 자연수 N과 P가 공백으로 구분되어 주어진다.
출력
첫째 줄에 반복되는 부분에 포함된 서로 다른 수의 개수를 출력한다.
제한
1 <= N <= 1,0002 <= P <= 97