【鸽巢原理+乱搞】
其实用不着开map
一步最巧妙的转化是……前缀和。
反正本宝宝突发奇想就出来了。
首先，我们分类讨论。
1.当∃i∈N+ 且 i∈[1,n] 使 ai|n 则直接选这个数就好
2.没有以上那种特殊情况的话，我们记录前缀和sumi=∑ik=1ak(mod n) 然后又有两种情况。
根据鸽巢抽屉原理，因为我们现在在(mod n)剩余系下，有n个数。所以只会有两种情况：
(1).当这n个数互不相等的时候，一定 ∃i∈N+ 且 i∈[1,n] 使 sumi≡0 (mod n)
则直接选1∼n 就好。
(2).如果有两个sum相等，假设为sumi,sumj ,j>i，则sumj−sumi≡0 (mod n)
而sumj−sumi=∑jk=iak 所以就可以选这 j−i 个数了。
一开始WA掉3次因为集合大小输出错了2333……qwq
上代码：
#include<iostream> #include<cstdio> #include<algorithm> #define int long long using namespace std; int n; int a[100100]; int sum[100010]; signed main() { scanf("%dll",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]),sum[i]=(sum[i-1]+a[i])%n; if(a[i]%n==0) {printf("1\n%lld",a[i]);return 0;} if(sum[i]==0) {printf("%lld\n",i);for(int j=1;j<=i;j++) printf("%lld\n",a[j]);return 0;} } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(sum[i]==sum[j]) { printf("%lld\n",j-i); for(int k=i+1;k<=j;k++) printf("%lld\n",a[k]); return 0; } return 0; }
