1103 N的倍数
- 1.0 秒
- 131,072.0 KB
- 20 分
- 3级题
一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。
例如：N = 8，数组A包括：2 5 6 3 18 7 11 19，可以选2 6，因为2 + 6 = 8，是8的倍数。
收起
输入
第1行：1个数N，N为数组的长度，同时也是要求的倍数。(2 <= N <= 50000) 第2 - N + 1行：数组A的元素。(0 < A[i] <= 10^9)
输出
如果没有符合条件的组合，输出No Solution。 第1行：1个数S表示你所选择的数的数量。 第2 - S + 1行：每行1个数，对应你所选择的数。
输入样例
8 2 5 6 3 18 7 11 19
输出样例
2 2 6
分析：
前缀和sum[i]%n总共有0~n-1这n种情况；
如果sum[i]=0，那么1~i的数之和就是N的倍数；
如果不存在sum[i]=0，那么根据抽屉原理，有n个前缀和，n-1种情况，那么一定存在sum[i]=sum[j]，那么i+1~j的数之和就是n的倍数
所以根本不会出现错误情况
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e18;
const int N = 500050;
const int MOD=1e9+7;
LL sum[N],a[N],vis[N];
LL ans,ans_l,ans_r,ans_size;
int main()
{int n,m;scanf("%d",&n);int flag=0;for(int i=1; i<=n; i++){scanf("%lld",&a[i]);sum[i]=(sum[i-1]%n+a[i]%n)%n;if(sum[i]%n==0){ans_size=i;flag=1;}vis[sum[i]]++;if(vis[sum[i]]>=2){ans_r=i;}}if(flag==1){printf("%lld\n",ans_size);for(int i=1; i<=ans_size; i++){printf("%lld\n",a[i]) ;}}else{for(int i=ans_r-1; i>=1; i--){if(sum[i]==sum[ans_r]){ans_l=i;break;}}printf("%lld\n",ans_r-ans_l+1);for(int i=ans_l+1; i<=ans_r; i++){printf("%lld\n",a[i]) ;}}return 0;
}