1049 数列的片段和 (20 分)

题目描述

给定一个整数序列和一个正整数P，请你编写一个程序，求出该序列中任意个连续数字的和中能被P整除的最大和。

输入格式：

输入第一行给出两个正整数N和P，其中N（≤10^5）是输入的数字个数，P（≤10^9）是给定的正整数。第二行给出N个不超过10^4的正整数，代表输入的序列。

输出格式：

在一行中输出最大的、能被P整除的连续数字和。

输入样例：

10 5
23 2 4 6 7 9 12 23 34 54

输出样例：

60

题目分析

这道题目可以使用前缀和的思想，将前i个数的和存储在sum[i]中，那么第i到j个数的和就可以表示为sum[j]-sum[i-1]，然后再对每个子序列求余数，如果余数为，那么就更新最大值。

代码如下：

相关问题

斐波那契数列1000000

斐波那契数列是一种数列，其中每一项都是前两项的和。根据引用【1】中的代码片段和引用【2】中的注释，我们可以看到这段代码用于计算斐波那契数列的第n项，并将结果除以10007取余数。在这个代码中，我们设置了一个数组F，用于存储斐波那契数列的每一项。代码中的for循环从第3项开始计算，通过递推公式F[i] = (F[i-1] + F[i-2]) % MOD来计算每一项的值。最后，输出F[n]的值作为斐波那契数列第n项除以10007的余数。

因此，斐波那契数列的第1000000项除以10007的余数是根据代码中的计算结果输出的。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [Python 改进斐波那契数列递归后，计算第1000万项只需4秒](https://blog.csdn.net/boysoft2002/article/details/120257133)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [Fibonacci数列](https://blog.csdn.net/lichenxi12321/article/details/19507255)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]

设计一个新的数列类，最多可容纳500个整型元素。除了可以在外部给定数列元素外，可具有查询子数列片段的功能。在主函数中以m a1,a2,a3...am的格式输入m个初始数列（第一个数为数列初始长度，后面m个数分别为m个数列元素），然后读取要查找的子数列，格式同完整数列，n,b1,b2,b3…bn。调用数列的设定方法保存完整数列，调用子数列查找方法返回子数列在完整数列中的起始位置(位置从0开始)，如不存在，则返回-1，在主函数中输出查找结果。 【输入形式】 完整数列和需要调用查询的子数列 【输出形式】 查

下是一份完整的代码实现，注释中有详细的解释：

#include <iostream>
using namespace std;

class Sequence {
private:
    int data[500]; // 数列
    int length; // 数列长度
public:
    Sequence() {
        length = 0;
    }
    void setData(int len, int *arr) { // 设置数列
        length = len;
        for (int i = 0; i < length; i++) {
            data[i] = arr[i];
        }
    }
    int find(int n, int *arr) { // 查找子数列
        if (n > length) { // 子数列长度大于数列长度，直接返回-1
            return -1;
        }
        for (int i = 0; i <= length - n; i++) { // 从数列头开始遍历，逐个判断是否存在该子数列
            bool isFind = true; // 标记是否找到该子数列
            for (int j = 0; j < n; j++) {
                if (data[i+j] != arr[j]) { // 如果存在不同的数，则表示该子数列不存在于该位置
                    isFind = false;
                    break;
                }
            }
            if (isFind) { // 如果找到该子数列，返回该子数列在数列中的起始位置
                return i;
            }
        }
        return -1; // 未找到该子数列，返回-1
    }
};

int main() {
    int m, n;
    Sequence seq;
    int arr[500];
    cin >> m;
    for (int i = 0; i < m; i++) { // 读取完整数列
        cin >> arr[i];
    }
    seq.setData(m, arr); // 设置数列
    cin >> n;
    for (int i = 0; i < n; i++) { // 读取子数列
        cin >> arr[i];
    }
    int pos = seq.find(n, arr); // 查找子数列
    cout << pos << endl; // 输出结果
    return 0;
}