Xorshift64
시간 제한2초메모리 제한512 MB
시작값 x로 생성한 xorshift64 수열에서 목표값 t가 처음 나타나는 위치(1부터 시작)를 구한다.
문제
Xorshift64는 1 이상 18,446,744,073,709,551,615 이하의 자연수로 이루어진 수열을 만들어내는 유사 난수 알고리즘이다. 이 수열의 주기는 18,446,744,073,709,551,615로, 1 이상 18,446,744,073,709,551,615 이하의 모든 자연수가 한 번씩 나온 다음에는 수열의 첫 번째 수가 다시 나온다.
아래는 수열의 첫 번째 수를 입력받아 Xorshift64 알고리즘에 의한 수열을 출력하는 C 코드이다.
#include <stdio.h>
#include <inttypes.h>
uint64_t xorshift64(uint64_t x) {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
int main(void) {
uint64_t x;
scanf("%" SCNu64, &x);
for (;;) {
printf("%" PRIu64 "\n", x);
x = xorshift64(x);
}
return 0;
}
예를 들어 88,172,645,463,325,252로 시작하는 수열은 다음과 같다.
88172645463325252, 8748534153485358512, 3040900993826735515, 3453997556048239312, 16431732851926010853, ...(18,446,744,073,709,551,608개 생략), 716875980015554409, 12211136061077133751, 88172645463325252, 8748534153485358512, 3040900993826735515, ...
이때 8,748,534,153,485,358,512는 이 수열에서 2번째에 처음으로 나오고, 716,875,980,015,554,409는 18,446,744,073,709,551,614번째에 처음으로 나온다.
사잇은 x로 시작하는 Xorshift64 수열에서 특정한 수 t가 몇 번째에 나오는지 예측할 수 있으면 좋겠다고 생각했다. 여러분이 사잇을 도와주자.
입력
첫째 줄에 두 개의 자연수 x와 t가 주어진다. (1 ≤ x, t ≤ 18,446,744,073,709,551,615)
출력
x로 시작하는 Xorshift64 수열에서 t가 처음으로 나오는 것은 몇 번째인지 출력한다.