目录
小蓝有一个长度为 n n n 的数组 A = ( a 1 , a 2 , ⋯ , a n ) A=\left(a_{1}, a_{2}, \cdots, a_{n}\right) A=(a1,a2,⋯,an), 数组的子数组被定义为从 原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数 组中所有元素的最大公约数。如果最多更改数组中的一个元素之后, 数组的最 大公约数为 g g g, 那么称 g g g 为这个数组的近似 GCD。一个数组的近似 GCD 可能 有多种取值。
具体的, 判断 g g g 是否为一个子数组的近似 GCD 如下:
如果这个子数组的最大公约数就是 g g g, 那么说明 g g g 是其近似 GCD。
在修改这个子数组中的一个元素之后 (可以改成想要的任何值), 子数 组的最大公约数为 g g g, 那么说明 g g g 是这个子数组的近似 GCD。
小蓝想知道, 数组 A A A 有多少个长度大于等于 2 的子数组满足近似 GCD 的值为 g g g.
输入的第一行包含两个整数
n
,
g
n,g
n,g，用一个空格分隔，分别表示数组
A
A
A 的长度和
g
g
g 的值。
第二行包含
n
n
n 个正数
a
1
,
a
2
,
⋯
,
a
n
,
a_1,a_2,⋯,a_n,
a1,a2,⋯,an, 相邻两个整数之间用一个空格分隔。
输出一行包含一个整数表示数组
A
A
A 有多少个长度大于等于 2 的子数组的近 似 GCD 的值为
g
g
g 。
5 3
1 3 6 4 10
5
2 ≤ n ≤ 1 0 5 , 1 ≤ g , a i ≤ 1 0 9 。 2≤n≤10^5,1≤g,ai≤10^9。 2≤n≤105,1≤g,ai≤109。
首先，如果一个数是g的倍数，那我们称其为符合条件的数。如果一个数组的近似GCD为
g
g
g，那么该数组最多只能有一个数不符合条件。为什么呢？因为如果只有一个不符合条件的数话，我们将其变为g，那么该数组的GCD将为g。如果数组全部符合条件呢？那我们只需要随便将其中一个数变为g，该数组的GCD也将为g。
那么现在问题就转换为存在多少个长度大于2的子数组使得子数组内最多只存在一个不符合条件的数，这个问题我们可以使用双指针解决。右指针r遍历数组的每一个数，左指针l将是以r将作为子数组的右端点的情况下，左端点能最远能到达的距离，也就是使得
[
l
,
r
]
[l,r]
[l,r]区间最多只存在一个不符合条件的数，且
l
l
l 和
r
r
r 之间的距离尽可能长。这样的话，数组
[
l
,
r
]
[l,r]
[l,r],
[
l
+
1
,
r
]
[l+1,r]
[l+1,r],
[
l
+
2
,
r
]
[l+2,r]
[l+2,r]…
[
r
−
1
,
r
]
[r-1,r]
[r−1,r]都是符合条件的答案，总共是r-l个。对于数组的每一个数我们都将其作为r后，累加答案即可。
我们考虑变换数组的值，如果其是符合条件的数，我们将其值赋为1，否则赋为0，对于区间
[
l
,
r
]
[l,r]
[l,r]是否为符合条件的子数组，只需要判断
s
u
m
[
l
,
r
]
sum[l,r]
sum[l,r]是否大于等于
r
−
l
r-l
r−l。求区间和
s
u
m
sum
sum，我们可以使用前缀和数组直接获取，但由于是双指针，也可以同时维护，这里代码使用了前缀和数组。
时间复杂度: O ( n ) O(n) O(n)。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
int n, g;
void solve()
{
cin >> n >> g;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
a[i] = (x % g == 0);
a[i] += a[i - 1];
}
int l = 0;
LL ans = 0;
for (int r = 2; r <= n; ++r) {
while (l + 1 < r && a[r] - a[l] < r - l - 1) l++;
ans += r - l -1;
}
cout << ans << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
n,g=map(int,input().split())
a=list(map(int,input().split()))
a=[0]+a
ans=0#记录上一个不符合条件的数
last=0#记录符合条件子数组的左区间
l=1
for r in range(1,n+1):
if a[r]%g!=0:
l=last+1
last=r
ans=ans+(r-l)
print(ans)
注意：本文主要掌握DCN自研无线产品的基本配置方法和注意事项，能够进行一般的项目实施、调试与运维AP基本配置命令AP登录用户名和密码均为：adminAP默认IP地址为：192.168.1.10AP默认情况下DHCP开启AP静态地址配置：setmanagementstatic-ip192.168.10.1AP开启/关闭DHCP功能：setmanagementdhcp-statusup/downAP设置默认网关：setstatic-ip-routegeteway192.168.10.254查看AP基本信息：getsystemgetmanagementgetmanaged-apgetrouteAP配
目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言： 在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC 已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析 这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy
我有这两个gcd函数的实现:defgcd1(a,b)ifa==baelsifa>bif(a%b)==0belsegcd1(a%b,b)endelseif(b%a)==0aelsegcd1(a,b%a)endendenddefgcd2(a,b)if(a==b)returnaelsifb>amin,max=a,belsemin,max=b,aendwhile(max%min)!=0min,max=max%min,minendminend函数gcd1是尾递归的，而gcd2使用while循环。我已经验证rubinius通过对阶乘函数进行基准测试来执行TCO，只有阶乘函数基准测试显示递归版本和迭
?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是： 如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。 如果m不为0，则将时读出来，然后将分读出来，如5
十四届蓝桥青少组模拟赛Python-20221108T1.二进制位数十进制整数2在十进制中是1位数，在二进制中对应10，是2位数。十进制整数22在十进制中是2位数，在二进制中对应10110，是5位数。请问十进制整数2022在二进制中是几位数？print(len(bin(2022))-2)#运行结果：11T2.晨跑小蓝每周六、周日都晨跑，每月的1、11、21、31日也晨跑。其它时间不晨跑。已知2022年1月1日是周六，请问小蓝整个2022年晨跑多少天？#样例代码1ls=[0,31,28,31,30,31,30,31,31,30,31,30,31]ans=0k=6foriinrange(1,13)
本文代码使用HAL库。文章目录前言一、MCP4017的重要特性二、MCP4017计算RBW阻值三、MCP4017地址四、MCP4017读写函数五、CubeMX创建工程（利用ADC测量MCP4017电压）、对应代码：总结前言一、MCP4017的重要特性蓝桥杯板子上的是MCP4017T-104ELT，如图1。MCP4017是一个可编程电阻，通过写入的数值可以改变电阻的大小。重点在于6引脚（W），5引脚（B&#
目录一、原理部分1、什么是串行通信（1）并行通信与串行通信（2）串行通信的制式（3）串行通信的主要方式 2、配置串口（1）SCON和PCON：串行口1的控制寄存器（2）SBUF：串行口数据缓冲寄存器 （3）AUXR：辅助寄存器编辑（4）ES、PS：与串行口1中断相关的寄存器（5）波特率设置 3、串口框架编写二、程序案例一、原理部分1、什么是串行通信（1）并行通信与串行通信微控制器与外部设备的数据通信，根据连线结构和传送方式的不同，可以分为两种：并行通信和串行通信。并行通信：数据的各位同时发送与接收，每个数据位使用一条导线，这种方式传输快，但是需要多条导线进行信号传输。串行通信：数据一位一
我有一个包含50K到100K字符串的字典(最多可以包含50个以上的字符)，我正在尝试查找给定字符串是否在具有“编辑”距离公差的字典中。(例如Levenshtein)。在进行搜索之前，我可以预先计算任何类型的数据结构。我的目标是尽快针对该字典运行数千个字符串并返回最近的邻居。如果有一个明显更快的算法，我会得到一个bool值来说明给定的是否在字典中为此，我首先尝试计算所有Levenshtein距离并取最小值，这显然非常慢。所以我尝试根据这篇文章实现一个LevenshteinTriehttp://stevehanov.ca/blog/index.php?id=114在这里查看我的重现基准的要
是否有Ruby库允许我对一组数据进行线性或非线性最小二乘法逼近。我想做的是:给定一系列[x,y]数据点针对该数据生成线性或非线性最小二乘法近似值库不必弄清楚它是否需要进行线性或非线性近似。库的调用者应该知道他们需要什么类型的回归我不想尝试移植某些C/C++/Java库来获得此功能，因此我希望有一些现有的Ruby库可供我使用。 最佳答案 尝试使用“statsample”gem。您可以使用下面提供的示例执行对数、指数、幂或任何其他转换。我希望这有帮助。require'statsample'#IndependentVariablex_da
问题描述小蓝负责一个公司的考勤系统,他每天都需要根据员工刷卡的情况来确定每个员工是否到岗。当员工刷卡时,会在后台留下一条记录,包括刷卡的时间和员工编号,只要在一天中员工刷过一次卡,就认为他到岗了。现在小蓝导出了一天中所有员工的刷卡记录,请将所有到岗员工的员工编号列出。输入格式输入的第一行包含一个正整数n,表示一天中所有员工的刷卡记录的条数。接下来n行,每行包含一条刷卡记录,每条刷卡记录的格式为:HH:MM:SSID其中HH:MM:SS表示刷卡时间,HH为一个0到23之间的两位十进制整数(可能含前导0)表示时,MM为一个0到59之间的两位十进制整数(可能含前导0)表示分,SS为一个0到59之间的