불필요한 수
시간 제한2초메모리 제한128 MB
N과 M이 주어질 때, 인접한 값끼리 더하는 과정을 반복해 얻은 최종 값(모듈로 M)에서 이항계수가 M으로 나누어져 영향이 없는 인덱스를 찾는 문제입니다.
문제
길이가 N인 수열 R[1], R[2], ..., R[N]이 있다. 각 원소는 0 이상 M 이하의 정수이다.
이 수열에 대해 다음 변환을 반복한다. 현재 수열의 길이가 L이면, 서로 이웃한 두 수의 합 A[1]+A[2], A[2]+A[3], ..., A[L-1]+A[L]로 이루어진 길이 L-1의 새 수열을 만든다. 길이가 1이 될 때까지 이 과정을 반복하고, 마지막에 남은 수를 M으로 나눈 나머지를 최종 값으로 정한다.
어떤 인덱스 i가 최종 값에 아무 영향을 주지 않는다면, 즉 R[i]의 값이 무엇이더라도 최종 값이 항상 같다면 i번째 수는 불필요한 수이다.
N과 M이 주어졌을 때, 불필요한 수의 개수와 그 인덱스들을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 N과 M이 주어진다.
1 <= N <= 100,000
2 <= M <= 1,000,000,000
출력
첫째 줄에 불필요한 수의 개수 K를 출력한다.
둘째 줄에 불필요한 수들의 인덱스를 오름차순으로 출력한다. K = 0이면 둘째 줄은 빈 줄이다.