代码拉取完成，页面将自动刷新
蓝桥杯题库 题目链接。
双指针
题意：
我们需要找的子数组需要满足以下两个条件:
使用双指针法，定义左指针 j 和右指针 i 分别表示：下标以 i 结尾，j ~ i-1开头的子数组都满足条件。
具体步骤如下:
nums[i] % g != 0时更新 last 和 j需要注意的点:
nums[i] % g != 0是用于判断 nums[i] 和 g 的最大公约数是否等于 g贡献法
参考：499.子串分值
求数组中每一个元素对结果 res 的贡献数。
具体步骤如下：
nums[i] % g == 0的元素变为 1 否则变为 0// 双指针 时间复杂度: O(n)
#include <iostream>
using namespace std;
int main()
{
int n, g;
cin >> n >> g;
int nums[n];
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int last = -1, j = 0;
long res = 0;
for (int i = 0; i < n; i++) {
if (nums[i] % g != 0) {
j = last + 1; // 左指针更新
last = i; // 记录当前右指针位置
}
res += (i-j);
}
cout << res << endl;
return 0;
}
// 双指针 时间复杂度: O(n)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long g = scan.nextLong();
long[] nums = new long[n];
for (int i = 0; i < n; i++) {
nums[i] = scan.nextLong();
}
int last = -1, j = 0;
long res = 0;
for (int i = 0; i < n; i++) {
if (nums[i] % g != 0) {
j = last + 1; // 左指针更新
last = i; // 记录当前右指针位置
}
res += (i-j);
}
System.out.println(res);
scan.close();
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
