gcd区间 (ST表)(爱思创算法四)
admin
2024-03-17 16:52:18
0次
前言:
本题为作业
题目描述
给定一行n个正整数a[1]..a[n]。
m次询问，
每次询问给定一个区间[L,R]，
输出a[L]..a[R]的最大公因数。
输入格式
第一行两个整数n，m。
第二行n个整数表示a[1]..a[n]。
以下m行，
每行2个整数表示询问区间的左右端点。
保证输入数据合法。
输出格式
共m行，每行表示一个询问的答案。
样例输入
5 3 4 12 3 6 7 1 3 2 3 5 5
样例输出
1 3 7
问题提示
对于30%的数据，n <= 100， m <= 10
对于60%的数据，m <= 1000
对于100%的数据，1 <= n <= 1000，1 <= m <= 1,000,000
解题思路
我们看题目是寻找 a[L]~a[R] 这片区间之内的一个最大公因数，
可以用ST表多次求解连续区域的最大公因数。
AC完整代码:
#include
using namespace std;
const int N=1e3+5;
int n,m,a[N],f[N][N];
int gcd(int x,int y)//最大公约数函数
{int i,j;while(y){int r=x%y;//辗转相除法x=y;y=r;}return x;
}
int main()
{int i,j,l,r;//套用ST表模板scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%d",&a[i]);f[i][i]=a[i];}for(i=1;i AC
上一篇：利物浦晒双红会海报：努涅斯C位，萨拉赫、远藤航出镜 利物浦晒双红会海报：努涅斯C位，萨拉赫、远藤航出镜
下一篇：克莱谈可能在附加赛战湖人：还有16场常规赛 在此之前不关注这些 克莱谈可能在附加赛战湖人：还有16场常规赛 在此之前不关注这些
相关内容
热门资讯
本地生活赛道要变天？某积分模式...
在高佣金、流量厮杀的传统平台夹击下，一个叫“伯位数智”的新模式悄悄冒头。它不靠砸钱补贴，也不玩算法霸...
原材料价格上涨，“魔芋第一股”...
2月26日，“魔芋第一股”一致魔芋发布的业绩快报显示，2025年，一致魔芋营收同比上涨19.91%至...
A股上市银行最年轻董事长来了！...
2月26日，宁波银行发布公告，宣布一系列人事变动。核心调整包括选举庄灵君为新任董事长，同意聘任冯培炯...
宝安区的火车站及机场都有哪些特...
宝安区作为深圳的重要区域，其火车站和机场不仅是交通枢纽，更是城市发展的重要窗口。它们各自以独特的特点...
2026 广州出口退税全解析：...
对于广州做出口生意的老板来说，出口退税绝对是降低成本、增加利润的关键，但很多人一提退税就头疼：流程复...
原创 一...
[赞]当下的黄金市场彻底火出了圈，涨价潮一波接一波，热门金饰身价暴涨数万元，各大品牌门店被抢购一空。...
原创 2...
房价调整这些年越来越明显，从二三线城市开始，现在一线也跟上了。郑州、石家庄那些地方房价从2022年就...
AI制药遇资本换挡，看懂数据才...
昨天和发小阿凯喝茶，他前两年脑热追了几个AI制药的早期项目，最近愁得连茶都喝不香——当初听着“AI颠...
【A股收评】三大指数涨跌不一，...
2月27日，三大指数涨跌不一，截至收盘，上证指数涨0.39%，深证成指跌0.06%，创业板指跌1.0...
不只软件工程师要用，谷歌加大力...
IT之家 2 月 27 日消息，据《商业内幕》今日报道，谷歌正在加大力度推动员工全面使用 AI，不仅...
原创 人...
这一回人民币升值又杀进了“六时代”，全网一片欢呼，有人说这证明中国经济正在强势反弹，也有人哀叹出口企...
大跳水！西安飞三亚低至350元...
春节假期过后不少航线的机票价格立刻“跳水”。 记者查询多个OTA平台发现，不少航线的票价不到1折。比...
“稀土荒”加剧！部分美国航天与...
财联社2月27日讯（编辑 潇湘）据行业知情人士对媒体透露，美国航空航天和半导体公司的供应商当前正面临...
君乐宝IPO加速，高端产品创新...
近年来，国民健康意识持续提升，科学饮食成为共识，乳制品行业迎来发展新机遇。正值行业发展向好的关键时期...
湖南码界领航教育科技有限公司：...
湖南码界领航教育科技有限公司：Python开发多元职业路径 在编程语言的世界里，Python凭借诸多...
突发利好！国产算力爆发，人民币...
在连续两天放量普涨后，今天A股开盘大跳水：昨天上海发布“沪九条”后资金兑现，房地产、建材板块大跌；津...
行业第一！成都又一企业冲刺港股...
记者了解到，主营业务为康养社区运营及医养结合服务。根据招股书，锦欣康养是中国庞大且快速增长的机构养老...
原创 俄...
乌俄战争已经迈入第五个年头，离第一次世界大战的总时长还差三个月又十四天。以目前局势来看，这场战争超越...
戴尔科技2026 财年业绩创历...
2 月 27 日，戴尔科技于 2 月 26 日发布 2026 财年第四财季及全年业绩（截至 2026...
提振消费：既要政策给力，也要改...
消费是最终需求，是我国经济增长的重要引擎。从国内看，我国经济已进入高质量发展阶段，多年来依靠大规模要...