首页 > 代码库 > [51NOD1103] N的倍数(鸽笼原理)
[51NOD1103] N的倍数(鸽笼原理)
题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1103
这题一脸组合数学鸽笼原理例题的样子。
这个问题自己其实YY过很久了,结果今天看到又给忘了。大概是因为没有手写过,希望下次不再忘了。
求前缀和,再对n取模。假如有模为0的,那么就直接拿出来前1~i个数。
如果没有0,那么模数只有n-1个,相对与一共有n个前缀和,根据鸽笼原理,必然有一个模数出现了两次,那这出现了两次的模数位置找出来,把这些数输出就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 500500; 6 int n; 7 LL a[maxn], s[maxn]; 8 int vis[maxn]; 9 10 void gao() { 11 for(int i = 1; i <= n; i++) { 12 if(!s[i]) { 13 printf("%d\n", i); 14 for(int j = 1; j <= i; j++) { 15 printf("%lld\n", a[j]); 16 } 17 return; 18 } 19 } 20 memset(vis, 0, sizeof(vis)); 21 for(int i = 1; i <= n; i++) { 22 if(vis[s[i]]) { 23 printf("%d\n", i - vis[s[i]]); 24 for(int j = vis[s[i]] + 1; j <= i; j++) { 25 printf("%lld\n", a[j]); 26 } 27 return; 28 } 29 vis[s[i]] = i; 30 } 31 } 32 33 int main() { 34 // freopen("in", "r", stdin); 35 while(~scanf("%d", &n)) { 36 memset(s, 0, sizeof(s)); 37 for(int i = 1; i <= n; i++) { 38 scanf("%lld", &a[i]); 39 s[i] = (s[i-1] + a[i]) % (LL)n; 40 } 41 gao(); 42 } 43 return 0; 44 }
[51NOD1103] N的倍数(鸽笼原理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。