51nod 1103 N的倍数 思路:抽屉原理+前缀和

时间:2023-03-10 05:09:29
51nod 1103 N的倍数 思路:抽屉原理+前缀和

题目:

51nod 1103 N的倍数 思路:抽屉原理+前缀和

这是一道很神奇的题目,做法非常巧妙。巧妙在题目要求n个数字,而且正好要求和为n的倍数。

思路:用sum[i]表示前i个数字的和%n。得到sum[ 1-N ]共N个数字。

   N个数字对N取模,每个数字都在0-( N-1 )之间。

   可能出现两种情况  1:有一个数字等于0。(都不相等)   2:至少有两个数字相等。

1.如果sum数组中有一个数字sum[i]=0,说明前i个数字的和为N的倍数。

2.如果sum[i]==sum[j],说明第i-( j-1 )或者( i+1 )-j的和为N的倍数。

只有1、2两种情况,不用考虑无解的情况。

#include <bits\stdc++.h>
using namespace std; int a[];
int visit[]; //visit[sum%n] != 0 说明有一个前缀和相等的,visit[sum%n]即为索引。
int main(){
int n;
cin >> n;
for(int i = ;i <= n; i++){
cin >> a[i];
} long long sum = ; //前缀和
for(int i = ;i <= n; i++){
sum = (sum + a[i])%n; //前缀和%n
if(sum != && visit[sum] == ){
visit[sum] = i; // 不等于0并且没有出现过,存在visit中
}else{
//等于0或者有相等的,开始输出结果,并结束程序
cout << i-visit[sum] << endl;
for(int j = visit[sum]+ ;j <= i; j++){
// cout <<"j:"<<j<<" "<< a[j] << " ";
cout << a[j] << endl;
}
break;
}
}
return ;
}
//writed by zhangjiuding