hdu 4648 Magic Pen 6

点击打开hdu 4648

思路: 扫描
分析:
1 设这列数前i项和为s[i],则一段连续的数的和 a[i]+a[i+1]+...+a[j-1]+a[j]=s[j]-s[i-1]，所以这段连续的数的和能被m整除的条件就是 (s[j]-s[i-1]) % m == 0，即 s[j]%m-s[i-1]%m == 0

2 因此，只需要每一个余数找使s[i]%m等于该余数的最小的i，和s[j]%m等于该余数的最大的j，相减即为最长的连续的数的长度
3 还要注意由于输入的n个数有负数，所以取模的时候应该注意数组的下标不能为负数

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;

int main(){
    int n , m;
    int num[MAXN];
    int pos[MAXN];
    while(scanf("%d%d" , &n , &m)  != EOF){
        for(int i = 1 ; i <= n ; i++) 
            scanf("%d" , &num[i]);
        int sum = 0;
        int ans = 0;
        memset(pos , 0 , sizeof(pos));
        for(int i = 1 ; i <= n ; i++){
            sum = ((sum+num[i])%m+m)%m;  
            if(sum == 0)
                ans = i;
            else if(pos[sum])
                ans = max(ans , i-pos[sum]);
            else
                pos[sum] = i;
        }
        printf("%d\n" , ans);
    }
    return 0;
}