时间限制： 1.0 秒
空间限制： 512 MiB
原题链接

解题思路：

题意分析

① 数据输入：

• 第一行输入一个整数 𝑛 (同学的数量)
• 第二行输入 n 个整数 a1, a2,…,an 代表 n 个同学的力量值

② 数据处理：

• gcd(ai, ai+1,…,ar) 使用折转相除法求最大公约数。
• 计算 f([l,r])=l x r x gcd(ai, ai+1,…,ar)。
• 计算所有 l,r 组合的价值之和 f([l,r])。

③ 数据输出：

• 将计算结果对 998244353 取模

思路一（暴力破解法）：

1、解题步骤拆分：
枚举所有的区间，在一个小的区间内计算最大公约数

思路二（动态规划）：

1、假设 nums={3,4,5,2} 如果我们记录了 {3,4,5} 的最大公约数为c，那么我们就能快速的计算 {3，4，5} 和 {2} 之间的最大公约数。

• 那我们就需要记录每种情况的最大公约数。
• 定义 dp[i][j] ,代表 nums 中下标 [i,j] 的最大公约数(i<=j，i 相当于 l。j 相当于 r)。
• dp数组初始化。dp[i][i] = nums[i] 。
• 可以通过dp[i][i]->dp[i][i+1]->dp[i][i+2]。
• 第一次计算连续 2 个数的最大公约数，再计算连续 3 个数的最大公约数，依次进行下去（每次将连续长度增加 1）。

代码实现

代码实现（思路一（暴力破解））：

#include<iostream>
#include<vector>
#include<bits/stdc++.h>  //万能头文件
using namespace std;

// 使用辗转相除法（欧几里得算法）计算两个数的最大公约数
int gcd(int a, int b) {
    while(b != 0) {  
        int temp = b;  // 临时存储 b
        b = a % b;     // 取 a 除 b 的余数
        a = temp;      // 将 b 赋值给 a
    }
    return a;  // 返回最大公约数
}

// 求数组中指定区间 [l, r] 的所有元素的最大公约数
int arrayGCD(const vector<int>& nums, int l, int r) {
    int ans_gcd = nums[l];  // 初始化 gcd 为区间的第一个元素
    for (int i = l + 1; i <= r; i++) {  // 遍历区间内的其他元素
        ans_gcd = gcd(ans_gcd, nums[i]);  // 更新当前区间的最大公约数
    }
    return ans_gcd;  // 返回最终的最大公约数
}


void Solution1(){
    int n;    // 同学的数量
    cin >> n;  // 输入同学数量

    // 定义数组 a 来存放 n 个同学的力量值
    vector<int> a(n);
    for (int i = 0; i < n; i++) {  
        cin >> a[i];  // 输入每个同学的力量值
    }

    int sumValue = 0;  // 用来存储区间的体育价值之和

    // 计算所有区间的体育价值之和
    // l 表示区间的起始位置，r 表示区间的结束位置
    for (int l = 0; l < n; l++) {  
        for (int r = l; r < n; r++) {  // 以 l 为起点，r 从 l 开始到 n
            // (l+1)*(r+1)*arrayGCD(a, l, r) 计算体育价值并累加
            sumValue += ((l + 1) * (r + 1) * arrayGCD(a, l, r)% 998244353 );  
        }
    }

    // 输出最终的结果，结果对 998244353 取模
    cout << sumValue << endl;
}

int main(int argc, char const *argv[]) {
    //暴力破解
    Solution1();
    //动态规划
    // Solution2();
    return 0;  
}

代码实现（思路二（动态规划））：

#include<iostream>
#include<vector>
#include<bits/stdc++.h>  //万能头文件
using namespace std;

// 使用辗转相除法（欧几里得算法）计算两个数的最大公约数
int gcd(int a, int b) {
    while(b != 0) {  
        int temp = b;  // 临时存储 b
        b = a % b;     // 取 a 除 b 的余数
        a = temp;      // 将 b 赋值给 a
    }
    return a;  // 返回最大公约数
}

void Solution2(){
    // 输入同学数量
    int n;    
    cin >> n;  

    // 定义数组 a 来存放 n 个同学的力量值
    vector<int> a(n);
    
    // 输入每个同学的力量值
    for (int i = 0; i < n; i++) {  
        cin >> a[i];  
    }

    // 用来存储区间的体育价值之和
    int sumValue = 0;  

    // 创建动态规划二维数组 dp，用来存储各区间的最大公约数
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // 初始化 dp 数组，dp[i][i] 为 a[i]，即区间长度为 1 时的最大公约数就是元素本身
    for (int i = 0; i < n; i++) {
        dp[i][i] = a[i];  // 单个元素的最大公约数就是它自己
        // 计算区间 [i, i] 的体育价值，累加到 sumValue 中
        sumValue += (i + 1) * (i + 1) * dp[i][i];  
    }

    // 动态规划计算所有长度大于 1 的区间的最大公约数
    for (int len = 2; len <= n; len++) {  // len 表示区间的长度，从 2 到 n
        for (int i = 0; i <= n - len; i++) {  // i 表示区间的起点
            int j = i + len - 1;  // j 表示区间的终点

            // 通过递推计算 dp[i][j]，即区间 [i, j] 的最大公约数
            dp[i][j] = gcd(dp[i][j - 1], a[j]);

            // 计算该区间的体育价值并累加到 sumValue 中
            sumValue = ((i + 1) * (j + 1) * dp[i][j] + sumValue) % 998244353;
        }
    }

    // 输出最终的结果，结果对 998244353 取模
    cout << sumValue << endl;
}

int main(int argc, char const *argv[]) {
    //暴力破解
    //Solution1();
    //动态规划
    Solution2();
    return 0;  
}

欢迎大家和我沟通交流(✿◠‿◠)