https://www.codechef.com/viewsolution/42129307
lets us suppose there are p numbers which are not divisible by k
we knoe that no which is already divisible by k cant be used in helpful way
so now after using all no there will be a last no which is alone and need to be divisible by k and can be made so by adding to itself
so that means all no must be able to do so by using itself only
so the no must be use itself
now at last
no will be of form 2 power x times no
so k need to divide by this
just random thought.
i was too using remainder of all to make the answer but realized that no changes doing so/