2704 问题 E: 蓝桥杯2022年第十三届决赛真题-近似 GCD（C/C++组）

 时间限制: 1s 内存限制: 256MB
题目描述

小蓝有一个长度为 n 的数组 A = (a1, a2, · · · , an)，数组的子数组被定义为从原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数组中所有元素的最大公约数。如果最多更改数组中的一个元素之后，数组的最大公约数为 g，那么称 g 为这个数组的近似 GCD。一个数组的近似 GCD 可能有多种取值。

具体的，判断 g 是否为一个子数组的近似 GCD 如下：

1. 如果这个子数组的最大公约数就是 g，那么说明 g 是其近似 GCD。

2. 在修改这个子数组中的一个元素之后（可以改成想要的任何值），子数组的最大公约数为 g，那么说明 g 是这个子数组的近似 GCD。

小蓝想知道，数组 A 有多少个长度大于等于 2 的子数组满足近似 GCD 的值为 g。

输入

输入的第一行包含两个整数 n, g，用一个空格分隔，分别表示数组 A 的长度和 g 的值。

第二行包含 n 个整数 a1, a2, · · · , an，相邻两个整数之间用一个空格分隔。

输出

输出一行包含一个整数表示数组 A 有多少个长度大于等于 2 的子数组的近似 GCD 的值为 g 。

样例输入

5 3
1 3 6 4 10

样例输出

5
提示

满足条件的子数组有 5 个：

[1, 3]：将 1 修改为 3 后，这个子数组的最大公约数为 3 ，满足条件。

[1, 3, 6]：将 1 修改为 3 后，这个子数组的最大公约数为 3 ，满足条件。

[3, 6]：这个子数组的最大公约数就是 3 ，满足条件。

[3, 6, 4]：将 4 修改为 3 后，这个子数组的最大公约数为 3 ，满足条件。

[6, 4]：将 4 修改为 3 后，这个子数组的最大公约数为 3，满足条件。

对于 20% 的评测用例，2 ≤ n ≤ 102 ；

对于 40% 的评测用例，2 ≤ n ≤ 103；

对于所有评测用例，2 ≤ n ≤ 105 , 1 ≤ g, ai ≤ 109。


                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
2025蓝桥杯系列真题系列中等题第16~20题
2025蓝桥杯系列真题系列中等题第16~20题
                        

                    

                

                

                    

                        
比赛状况