AtCoder Beginner Contest竞赛题解 | 洛谷 AT_abc435_b No-Divisible Range

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总

---

【题目来源】

洛谷：[AT_abc435_b ABC435B] No-Divisible Range - 洛谷

【题目描述】

You are given a sequence of positive integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ .
Find the number of pairs of integers $ (l,r) $ satisfying $ 1\leq l\leq r\leq N $ that satisfy the following condition:

For every integer $ i $ satisfying $ l\leq i\leq r $ , $ A_i $ isnota divisor of $ A_l+A_{l+1}+\cdots+A_r $ .

【输入】

The input is given from Standard Input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

【输出】

Output the answer.

【输入样例】

5 8 6 10 5 7

【输出样例】

6

【算法标签】

《洛谷 AT_abc435_b No-Divisible Range》 #枚举#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=55;// 最大数组长度intn;// 数组长度intans;// 答案：符合条件的区间数量inta[N];// 原始数组intsa[N];// 前缀和数组，sa[i]=a[1]+a[2]+...+a[i]/** * 检查区间[l,r]的和是否能被区间内任意一个数整除 * @param res 区间和 * @param l 区间左端点 * @param r 区间右端点 * @return 如果区间和不能被区间内任意数整除，返回true；否则返回false */boolcheck(intres,intl,intr){// 遍历区间[l,r]内的每个数for(inti=l;i<=r;i++){// 如果区间和能被a[i]整除，则不符合条件if(res%a[i]==0){returnfalse;}}// 区间和不能被区间内任意数整除returntrue;}intmain(){// 输入数组长度cin>>n;// 输入数组并计算前缀和for(inti=1;i<=n;i++){cin>>a[i];sa[i]=sa[i-1]+a[i];// 前缀和}// 枚举所有区间[i,j]for(inti=1;i<=n;i++){for(intj=i;j<=n;j++){// 计算区间[i,j]的和inttot=sa[j]-sa[i-1];// 调试输出// cout << "tot " << tot << endl;// 检查区间和是否能被区间内任意数整除if(!check(tot,i,j)){continue;// 不符合条件，跳过}// 调试输出// cout << "i j " << i << " " << j << endl;// 符合条件，计数加1ans++;}}// 输出结果cout<<ans<<endl;return0;}

【运行结果】

5 8 6 10 5 7 6