Unnecessary Numbers
Time limit2sMemory limit128 MB
Given N and M, determine which indices in a length-N sequence have coefficient divisible by M in the final repeated-adjacent-sum value modulo M, using binomial coefficient properties.
- Level
Medium7 of 10
- Topics
- Math, Number theory, Combinatorics
- Solved
- No attempts yet
Problem
There is a sequence R[1], R[2], ..., R[N] of length N. Each element is an integer from 0 to M, inclusive.
Repeat the following transformation. If the current sequence has length L, replace it with the length L-1 sequence of adjacent sums: A[1]+A[2], A[2]+A[3], ..., A[L-1]+A[L]. Continue until only one number remains, then take that number modulo M as the final value.
An index i is unnecessary if it never affects the final value; that is, the final value is always the same no matter what value R[i] has.
Given N and M, write a program that finds how many indices are unnecessary and which indices they are.
Input
The first line contains two integers N and M.
1 <= N <= 100,000
2 <= M <= 1,000,000,000
Output
Print the number K of unnecessary indices on the first line.
On the second line, print the unnecessary indices in increasing order. If K = 0, the second line is empty.