시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 66 26 24 48.000%

문제

현재 사용되고 있는 폰노이만 컴퓨터에서는 난수(random number)를 만들어낼 수 없다. 따라서 난수를 얻고자 할 때는 수들을 규칙적으로, 하지만 뒤섞인 순서로 나열하는 방법을 사용한다. 실수 범위의 난수는 다루기가 복잡하므로, 이 문제에서는 음 아닌 정수만을 고려하자.

당신은 좀 더 난수에 가까운 수를 얻고자 다음과 같은 방법을 고안했다. 당신은 0이상 M이하의 난수를 얻고 싶은데, 이를 위해 0이상 M이하의 난수 N개 R[1], R[2], …, R[N]을 만든다. 다음으로 이 수열에서 인접한 두 수들의 합으로 된 합수열을 만든다. 위의 수열의 합수열은 R[1]+R[2], R[2]+R[3], …, R[N-1]+R[N]이 된다. 이와 같은 합수열을 만들면 수열의 길이가 N-1이 되는데, 합수열의 합수열을 구하는 과정을 반복하여 합수열의 길이가 1이 될 때까지, 즉 한 개의 수가 남을 때까지 반복한다. 이 때 남은 수를 M으로 나눈 나머지를 구하면 우리가 만들고자 하는 난수가 된다.

하지만 이와 같은 방법에서, 어떤 N과 M에 대해서는 불필요한 수가 생기기도 한다. R[i] (1≤i≤N)가 어떤 값이더라도 최종적으로 얻은 난수가 같다면 i번째 수는 불필요한 수가 된다. 예를 들어 N=3, M=2일 때는 R[2]의 값에 상관없는 난수가 만들어진다.

N과 M이 주어졌을 때 불필요한 수의 개수를 세고, 구체적으로 어떤 수들이 불필요한 수인지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N(1≤N≤100,000), M(2≤M≤1,000,000,000)이 주어진다.

출력

첫째 줄에 불필요한 수의 개수 K를 출력한다. 다음 줄에는 불필요한 K개의 수들의 index(위에서의 i)를 출력한다. index는 순서대로 출력한다.

예제 입력

3 2

예제 출력

1
2

힌트