20121 - 카드 셔플

step 1

카드가 $N$장 있을 때 제일 위를 0번째 카드, 제일 밑을 $N-1$번째 카드라고 합시다. $X$셔플을 한번 하면 $X$번째 카드는 $(X*2)\%N$으로 이동합니다. $Y$셔플을 한번 하면 $X$번째 카드는 $(X*2+1)\%N$으로 이동합니다.

step 2

처음 카드가 $X$번째에 있다고 가정합니다. 한 번의 셔플을 했을 때 카드는 $(X*2)\%N\sim (X*2+1)\%N$에 있을 수 있습니다. 한번 더 셔플을 하면 $(X*4)\%N\sim (X*4+3)\%N$에 있을 수 있습니다. 한번 할 때마다 있을 수 있는 위치가 2배씩 늘어납니다. 그럼 대략 30번의 셔플을 하면 모든 위치를 커버할 수 있습니다.

만약 목표하는 위치를 커버하게 되면 이 과정을 역으로 올라가면서 어떤 셔플을 해야 하는지 알아낼 수 있습니다. 

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
long long int b[200];
int main() {
    long long int s, e,n,x,ss,ee,c,cnt,i;
    scanf("%lld", &n);
    while (n--) {
        scanf("%lld%lld%lld", &x, &s, &e);
        s--; e--;
        ss = s; ee = s;
        c = 1;
        cnt = 0;
        while (1) {
            if (ss <= ee) {
                if (ss <= e && e <= ee) break;
            }
            else {
                if (ss <= e || e <= ee) break;
            }
            ss *= 2;
            ee *= 2;
            ee++;
            ss %= x;
            ee %= x;
            c *= 2;
            cnt++;
            if (c >= x) break;
        }
        if (e < ss) e += x;
        e -= ss;
        for (i = 1;i <= cnt;i++) {
            b[i] = e%2;
            e /= 2;
        }
        for (i = cnt;i >= 1;i--) {
            if (b[i] == 1) printf("Y"); else printf("X");
        }
        printf("\n");
    }
    return 0;
}