ural 1032 Find a Multiple

我们用A[i]记录每一个数, 用sum[i]记录从1到i的各数之和余n, T[i]记录上一个和的余数为i出现的地方.

那么每次有以下几种情况:

1, sum[i]==0, 则区间为1到i;

2, T[sum[i]]!=0, 则区间为T[sum[i]]+i到i;

3, T[sum[i]]==0, 记录T[sum[i]]=i.

#include <iostream> using namespace std; int n,A[10001]; int sum[10001]; int T[10001]; int main() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&A[i]); for(i=1;i<=n;i++) { sum[i]=(A[i]+sum[i-1])%n; if(T[sum[i]]||sum[i]==0) { printf("%d/n",i-T[sum[i]]); for(j=T[sum[i]]+1;j<=i;j++) printf("%d/n",A[j]); break; } T[sum[i]]=i; } return 0; }