poj 2356 Find a multiple(鸽巢原理+标记)

• qiurisiyu 发布于
• 1184 收藏

题目：http://poj.org/problem?id=2356 大意：给出n个数字，在其中找出连续的数字使其和是n的倍数，不能找到输出0。 设sum[i]=a1+a2+……+ai,n个sum[i]模n的结果范围是[0,n-1]。由鸽巢原理可知：必有一个sum[i]的模结果是0（均匀分布）或有两个sum[i]模结果相等（非均匀分布）（也就是sum[j]-sum[i]=0）。所以一定存在着这样连续...