蓝桥杯2727: 蓝桥杯2022年第十三届决赛真题-近似 GCD(Python组)题解

2拍不死你 算法基础篇 82 0
题库丰富多样,涵盖各个领域,全网最全C++题库,让您在练习中不断成长!
小蓝有一个长度为 n 的数组 A = ,数组的子数组被定义为从原数组中选出连续的一个或多个元素组成的数组,数组的最大公约数指的是数组中所有元素的最大公约数,如果最多更改数组中的一个元素之后,数组的最大公约数为 g,那么称 g 为这个数组的近似 GCD,一个数组的近似 GCD 可能有多种取值。

小蓝有一个长度为 n 的数组 A = (a1, a2, · · · , an),数组的子数组被定义为从原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数组中所有元素的最大公约数。如果最多更改数组中的一个元素之后,数组的最大公约数为 g,那么称 g 为这个数组的近似 GCD。一个数组的近似 GCD 可能有多种取值。 具体的,判断 g 是否为一个子数组的近似 GCD 如下: 1. 如果这个子数组的最大公约数就是 g,那么说明 g 是其近似 GCD。 2. 在修改这个子数组中的一个元素之后(可以改成想要的任何值),子数组的最大公约数为 g,那么说明 g 是这个子数组的近似 GCD。 小蓝想知道,数组 A 有多少个长度大于等于 2 的子数组满足近似 GCD 的值为 g。

蓝桥杯2727: 蓝桥杯2022年第十三届决赛真题-近似 GCD(Python组)题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
全网最全C++题库,助您挑战自我,突破极限,成为编程领域的佼佼者!

标签: 蓝桥杯2727: 蓝桥杯2022年第十三届决赛真题-近似 GCD(Python组)题解