Xorshift32
시간 제한1초메모리 제한256 MB
시작값 x와 목표값 t가 주어질 때, Xorshift32 의사난수 수열에서 t가 처음 나타나는 위치를 구한다.
문제
Xorshift32는 1 이상 4,294,967,295 이하의 자연수로 이루어진 수열을 만들어내는 유사 난수 알고리즘이다. 이 수열의 주기는 4,294,967,295로, 1 이상 4,294,967,295 이하의 모든 자연수가 한 번씩 나온 다음에는 수열의 첫 번째 수가 다시 나온다.
아래는 수열의 첫 번째 수를 입력받아 Xorshift32 알고리즘에 의한 수열을 출력하는 C 코드이다.
#include <stdio.h>
#include <inttypes.h>
uint32_t xorshift32(uint32_t x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return x;
}
int main(void) {
uint32_t x;
scanf("%" SCNu32, &x);
for (;;) {
printf("%" PRIu32 "\n", x);
x = xorshift32(x);
}
return 0;
}
예를 들어 2,463,534,242로 시작하는 수열은 다음과 같다.
2463534242, 723471715, 2497366906, 2064144800, 2008045182, ...(4,294,967,288개 생략), 1232801914, 1174207936, 2463534242, 723471715, 2497366906, ...
이때 723,471,715는 이 수열에서 2번째에 처음으로 나오고, 1,232,801,914는 4,294,967,294번째에 처음으로 나온다는 사실을 알 수 있다.
사잇은 x로 시작하는 Xorshift32 수열에서 특정한 수 t가 몇 번째에 나오는지 예측할 수 있으면 좋겠다고 생각했다. 여러분이 사잇을 도와주자.
입력
첫째 줄에 두 개의 자연수 x와 t가 주어진다. (1 ≤ x, t ≤ 4,294,967,295)
출력
x로 시작하는 Xorshift32 수열에서 t가 처음으로 나오는 것은 몇 번째인지 출력한다.