시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 7 5 5 83.333%

문제

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가 몇 번째에 나오는지 예측할 수 있으면 좋겠다고 생각했습니다. 여러분이 사잇을 도와주세요.

입력

첫째 줄에 두 개의 자연수 xt가 주어집니다. (1 ≤ x, t ≤ 18,446,744,073,709,551,615)

출력

x로 시작하는 Xorshift64 수열에서 t가 처음으로 나오는 것은 몇 번째인지 출력합니다.

예제 입력 1

88172645463325252 8748534153485358512

예제 출력 1

2

예제 입력 2

88172645463325252 716875980015554409

예제 출력 2

18446744073709551614

출처