问题 H: 能被M整除的 一段和

Question

描述

N个正整数，如果连续的一段(可能是一个数)和能被M整除，输出这一段的开始位置和结束位置。如果答案有多段，输出结束位置最前面的一段。

输入

第一行：2个正整数N和M，范围1<M<N<100000。

第二行：N个正整数，每个数范围[1,10000]。

输出

2个正整数。

样例输入 复制
5 6
1 2 2 2 6
样例输出 复制
2 4
提示
解释：第2个到第4个数的和是2+2+2=6

错误的分数：33
错误的代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],sum[100005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    if(m>sum[n]) printf("1 %d",n);
    int s;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        {
            s=sum[j]-sum[i-1];
            if(s%m==0)
            {
                printf("%d %d",i,j);
                return 0;
            }
        }
    return 0;
}

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题 H: 能被M整除的一段

描述：N个正整数，如果连续的一段(可能是一个数)和能被M整除，输出这一段的开始位置和结束位置。如果答案有多段，输出结束位置最前面的一段。

输入：第一行：2个正整数N和M，范围1<M<N

解答

#include <iostream>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int start = 0, end = 0;
    int sum = 0;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        sum += num;
        if (sum % M == 0) {
            if (i == 0) {
                start = 1;
            } else {
                start = i - (sum - num) / M + 1;
            }
            end = i;
            break;
        }
    }
    if (end == 0) {
        cout << "No segment" << endl;
    } else {
        cout << start << " " << end << endl;
    }
    return 0;
}

说明

本题可以使用一个累加和来解决。遍历每个数，如果累加和能被M整除，就输出当前段的开始位置和结束位置。如果累加和不能被M整除，就继续遍历下一个数。