衡水市网站建设_网站建设公司_Bootstrap_seo优化

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

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

适合人群：

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

附上汇总贴：学而思编程周赛普及奠基组 | 汇总

T1 数字游戏

【题目来源】

数字游戏

【题目描述】

小美和小猴决定玩一个数字游戏。

小美在纸上写下n nn个数字a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​，小猴则会写下一个数字q qq。

由于小美最近复习离散数学，所以她想要和小猴玩一个有关于互质的游戏。一般来说，如果两个数x xx和y yy的最大公约数为1 11，我们就说x xx和y yy是互质的，简记为x ⊥ y x⊥yx⊥y。

具体来说，小美会询问小猴一共m mm个问题，每次询问，小美会问小猴一段连续的区间l ∼ r l∼rl∼r内有多少个数与小猴所写下的数字q qq互质。

由于小美写的数字太多了，所以小猴想请求你的帮助，你能回答小美的问题吗？

【输入】

第一行，包含三个整数n , m , q n,m,qn,m,q。
第二行，包含n nn个整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​。
接下来m mm行，每行两个整数l , r l,rl,r，表示这一次小美询问的区间。

【输出】

输出m mm行，每行一个整数，表示小美本次询问的区间。

【输入样例】

5 3 2 1 2 3 4 5 1 3 2 4 1 5

【输出样例】

2 1 3

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intn,m,q;inta[N],sa[N];intgcd(inta,intb){returnb?gcd(b,a%b):a;}intmain(){cin>>n>>m>>q;// 输入数组长度n，查询次数m，和给定的数qfor(inti=1;i<=n;i++){intx;cin>>x;if(gcd(x,q)==1)// 如果x和q互质a[i]=1;// 标记为1}// 构建前缀和数组for(inti=1;i<=n;i++)sa[i]=sa[i-1]+a[i];// 处理查询while(m--){intl,r;cin>>l>>r;cout<<sa[r]-sa[l-1]<<endl;// 输出区间[l, r]中与q互质的数的个数}return0;}

【运行结果】

5 3 2 1 2 3 4 5 1 3 2 2 4 1 1 5 3