1103 N的倍数

一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。 例如：N = 8，数组A包括：2 5 6 3 18 7 11 19，可以选2 6，因为2 + 6 = 8，是8的倍数。 Input 第1行：1个数N，N为数组的长度，同时也是要求的倍数。(2 <= N <= 50000) 第2 - N + 1行：数组A的元素。(0 < A[i] <= 10^9) Output 如果没有符合条件的组合，输出No Solution。 第1行：1个数S表示你所选择的数的数量。 第2 - S + 1行：每行1个数，对应你所选择的数。 Input示例 8 2 5 6 3 18 7 11 19 Output示例 2 2 6 题解：找mod上n等于0的连续区间就可以了。因为，先把前缀和搞出来（mod上n），那么出现的n个数一定是0~n-1，如果存在某个为0的，那就是答案了；如果不存在为0的，那么根据鸽舍定理，有n个数，但是区间为[1,n-1]，所以必定有两个位置出现同一个值，而对于前缀和，两个值相同，意味着两个值夹着的区间之和为0。

代码：

#include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <string> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <cmath> #include <ctime> using namespace std; typedef long long ll; typedef pair<ll, int> P; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; const double PI = acos(-1.0); const double eps = 1e-10; const int maxn = 1e6+7; const int mod = 1e9+7; int n; int a[maxn]; int vis[maxn]; int main() { scanf("%d",&n); int res = 0; memset(vis,-1,sizeof(vis)); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); vis[0] = 0; for(int i = 1;i <= n;i++){ res = (res+a[i])%n; if(vis[res]!=-1){ printf("%d\n",i-vis[res]); for(int j = vis[res]+1;j <= i;j++){ printf("%d\n",a[j]); } return 0; } vis[res] = i; } puts("No Solution"); return 0; } 涉及知识点：

1、鸽舍定理。

2、约数倍数与mod。