poj2356:Find a multiple

題目連結：

【鴿巢原理+亂搞】

其實用不着開$map$

一步最巧妙的轉化是$……$字首和。

反正本寶寶突發奇想就出來了。

首先，我們分類讨論。

1.當$∃i \in N_{+} $ 且 $i \in [1,n]$ 使 $a_{i} | n$ 則直接選這個數就好

2.沒有以上那種特殊情況的話，我們記錄字首和$sum_{i}= \sum _{k=1}^{i} a_{k} (mod \ \ n)$ 然後又有兩種情況。

根據鴿巢抽屜原理，因為我們現在在$(mod \ \ n)$剩餘系下，有$n$個數。是以隻會有兩種情況：　

　　(1).當這$n$個數互不相等的時候，一定 $∃i \in N_{+} $ 且 $i \in [1,n]$ 使 $sum_{i} \equiv 0 \ \ (mod \  n)$

　　　　 則直接選$1 \thicksim n$ 就好。

　　(2).如果有兩個$sum$相等，假設為$sum_{i},sum_{j} \ ,j>i$，則$sum_{j}-sum_{i} \equiv 0 \ \ (mod \ n)$

　　　　而$sum_{j}-sum_{i} =  \sum_{k=i}^{j} a_{k} $ 是以就可以選這 $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;
}