ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1032. Find a Multiple

Explanation why continuous segment is always there whose sum is divisible by n
Posted by Vineet Jain 7 Dec 2020 23:59
Let suppose there is prefix sum array with mod n is pre1,pre2,......,pren. Since there can be only n-1 numbers present except zero. If zero is one of elements in prefix sum array then answer is already 0 to i. Else If zero is not present then some number should repeat because prefix array is of size n but only 1,2.... n-1 numbers are present. So there should be particular i,j => prei==prej. Therefore from i+1 to j segment will be divisible by n.

Edited by author 08.12.2020 00:01