SOJ 2293: http://acm.scu.edu.cn/soj/problem.action?id=2293
题目意思很明白, 找出能被给出的整数整除的最长的连续子段和, 输出这个子段和的长度. 算法思路很简单: 对数组累计求和, 然后利用模同余的思想. 这里有个取模的 trick 注意一下, C++ 中一个负数 x 对一个正数 y 取模为负, 例如 - 9%4=-1. 为了避免负余数, 我们可以用 (x%y y)%y.
代码如下:
- #include<iostream>
- #include<cstring>
- using namespace std;
- int main()
- {
- int n, m;
- int i;
- int mod[10005];
- int temp;
- long long sum;
- int result;
- int id;
- while (scanf("%d%d", &n, &m) == 2)
- {
- memset(mod, -1, sizeof(mod));
- sum = 0;
- result = 0;
- mod[0] = 0;
- for (i = 1; i <= n; i++)
- {
- scanf("%d", &temp);
- sum = sum + temp;
- id=(sum%m + m) % m;
- if (mod[id] == -1)
- mod[id] = i;
- else
- {
- if (i - mod[id]> result)
- result = i - mod[id];
- }
- }
- printf("%d\n", result);
- }
- return 0;
- }
- View Code
参考以下博文:
来源: http://www.bubuko.com/infodetail-2972012.html