兰州市生态建设管理局网站,北京市住房城乡建设部网站首页,网站建设首页,免费天眼查公司查询目录1.近似GCD1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围7.原题链接2.解题思路3.Ac_code1.C2.Python1.近似GCD
1.题目描述
小蓝有一个长度为 nnn 的数组 A(a1,a2,⋯,an)A\left(a_{1}, a_{2}, \cdots, a_{n}\right)A(a1,a2,⋯,an), 数组的子数组被定…
目录1.近似GCD1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围7.原题链接2.解题思路3.Ac_code1.C2.Python1.近似GCD
1.题目描述
小蓝有一个长度为 nnn 的数组 A(a1,a2,⋯,an)A\left(a_{1}, a_{2}, \cdots, a_{n}\right)A(a1,a2,⋯,an), 数组的子数组被定义为从 原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数 组中所有元素的最大公约数。如果最多更改数组中的一个元素之后, 数组的最 大公约数为 ggg, 那么称 ggg 为这个数组的近似 GCD。一个数组的近似 GCD 可能 有多种取值。
具体的, 判断 ggg 是否为一个子数组的近似 GCD 如下:
如果这个子数组的最大公约数就是 ggg, 那么说明 ggg 是其近似 GCD。
在修改这个子数组中的一个元素之后 (可以改成想要的任何值), 子数 组的最大公约数为 ggg, 那么说明 ggg 是这个子数组的近似 GCD。
小蓝想知道, 数组 AAA 有多少个长度大于等于 2 的子数组满足近似 GCD 的值为ggg.
2.输入格式
输入的第一行包含两个整数 n,gn,gn,g用一个空格分隔分别表示数组 AAA 的长度和 ggg 的值。 第二行包含 nnn 个正数 a1,a2,⋯,an,a_1,a_2,⋯,a_n,a1,a2,⋯,an, 相邻两个整数之间用一个空格分隔。
3.输出格式
输出一行包含一个整数表示数组 AAA 有多少个长度大于等于 2 的子数组的近 似 GCD 的值为 ggg 。
4.样例输入
5 3 1 3 6 4 10
5.样例输出
5
6.数据范围
2≤n≤105,1≤g,ai≤109。2≤n≤10^5,1≤g,ai≤10^9。2≤n≤105,1≤g,ai≤109。
7.原题链接
近似GCD
2.解题思路
首先如果一个数是g的倍数那我们称其为符合条件的数。如果一个数组的近似GCD为 ggg那么该数组最多只能有一个数不符合条件。为什么呢因为如果只有一个不符合条件的数话我们将其变为g那么该数组的GCD将为g。如果数组全部符合条件呢那我们只需要随便将其中一个数变为g该数组的GCD也将为g。
那么现在问题就转换为存在多少个长度大于2的子数组使得子数组内最多只存在一个不符合条件的数这个问题我们可以使用双指针解决。右指针r遍历数组的每一个数左指针l将是以r将作为子数组的右端点的情况下左端点能最远能到达的距离也就是使得[l,r][l,r][l,r]区间最多只存在一个不符合条件的数且 lll 和 rrr 之间的距离尽可能长。这样的话数组[l,r][l,r][l,r],[l1,r][l1,r][l1,r],[l2,r][l2,r][l2,r]…[r−1,r][r-1,r][r−1,r]都是符合条件的答案总共是r-l个。对于数组的每一个数我们都将其作为r后累加答案即可。
但是对于每个数的上界l我们该如何考虑呢如果是符合条件的数那么它的上界是上两个不符合条件的数的下一个数。就比如下标c是符合条件的数在它之前上一个不符合条件的数下标是b再往前一个不符合条件的数的下标为a那么c的上界下标l应该指向a1。如果是不符合条件的数那么很明显它的上界应该是上一个不符合条件的数的下一个数。 同样假设下标c的上一个不符合条件的数的下标为b那么它的上界就应该是b1。明白了这个过程后我们使用变量last来记录上一次不符合条件的数的位置每次遇到不符合条件的数就将l和last更新。
当然上述双指针做法过于抽象我们考虑变换数组的值如果其是符合条件的数我们将其值赋为1否则赋为0对于区间[l,r][l,r][l,r]是否为符合条件的子数组只需要判断 sum[l,r]sum[l,r]sum[l,r]是否大于等于 r−lr-lr−l。求区间和 sumsumsum我们可以使用前缀和数组直接获取但由于是双指针也可以同时维护这里代码使用了前缀和数组。
时间复杂度:O(n)O(n)O(n)。
3.Ac_code
1.C
代码1:
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int N100010;int n,g;
int a[N];int main()
{scanf(%d%d,n,g);for(int i1;in;i){scanf(%d,a[i]);}LL ans0;//记录上一个不符合条件的数int last0;//记录符合条件子数组的左区间int l1;for(int r1;rn;r){//判断它是否是符合条件的数bool ta[r]%g0;if(!t){//时刻保证区间内不符合条件的数只能有一个llast1,lastr;}//累加答案ansr-l;}printf(%lld\n,ans);return 0;
}代码2
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairint, 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::vectorint 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;
}2.Python
n,gmap(int,input().split())
alist(map(int,input().split()))
a[0]a
ans0#记录上一个不符合条件的数
last0#记录符合条件子数组的左区间
l1
for r in range(1,n1):if a[r]%g!0:llast1lastransans(r-l)
print(ans)
