b_51_N的倍数（抽屉原理+前缀和）

一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。
2<=N<=50000；0<A[i]<=10^9

思路：A[i]对N取模的结果为1~N-1（共N-1个数)，而A有N个数，这就说明这些模N的数中至少有两个数是一样的（抽屉原理保证了数据一定有解)；然后就是分两种情况：

• 前缀和s[0:i]中有0出现，则输出A[0~i]
• 否则，如果存在两个前缀s[i]和s[j]（i!=j）和它们的值相等，则证明s[j...i]这一段一定是n的倍数（模n为0）

这里咬注意啊：下标从0开始的话如果第一个数就是n的倍数，需要特判一下，因为这句：cout<<i-j<<‘\n‘;

#include<bits/stdc++.h>
#define rep1(i,s,e) for( int i=s;i<=e;i++)
#define rep2(i,s,e) for( int i=e;i>=s;i--)
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll n,s,a[N],mp[N];
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n; rep1(i,1,n) cin>>a[i];
    //mp[0]=0;
    rep1(i,1,n) {
        s=(s+a[i])%n;
        if (s==0 || mp[s]) {
            int j=mp[s];
            cout<<i-j<<‘\n‘; 
            rep1(k,j+1,i) cout<<a[k]<<‘\n‘;
            break;
        } else {
            mp[s]=i;
        }
    }
    return 0;
}

b_51_N的倍数（抽屉原理+前缀和）

原文：https://www.cnblogs.com/wdt1/p/13872430.html