博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷1890 gcd区间
阅读量:5828 次
发布时间:2019-06-18

本文共 994 字,大约阅读时间需要 3 分钟。

题目描述

给定一行n个正整数a[1]..a[n]。
m次询问,每次询问给定一个区间[L,R],输出a[L]..a[R]的最大公因数。

输入输出格式

输入格式:

第一行两个整数n,m。
第二行n个整数表示a[1]..a[n]。
以下m行,每行2个整数表示询问区间的左右端点。
保证输入数据合法。

输出格式:

共m行,每行表示一个询问的答案。

输入输出样例

输入样例#1:

5 34 12 3 6 71 32 35 5

输出样例#1:

137

说明

对于30%的数据,n <= 100, m <= 10
对于60%的数据,m <= 1000
对于100%的数据,1 <= n <= 1000,1 <= m <= 1,000,000
0 < 数字大小 <= 1,000,000,000

解题思路

这个题用的类似区间型DP,但是只能过8个点,求优化,求优化

1 program gcd1;   2 var   3 f:array[1..1000,1..1000] of longint;   4 n,m,i,j,l,r,p:Longint;   5 function gcd(x,y:Longint):longint;   6 begin   7     if x mod y=0 then exit(y)   8     else exit(gcd(y,x mod y));   9 end;  10 begin  11     read(n,m);  12     for i:=1 to n do read(f[i,i]);  13     for p:=1 to n-1 do  14         for i:=1 to n-p do  15         begin  16             j:=i+P;  17             f[i,j]:=gcd(f[i,j-1],f[i+1,j]);  18         end;  19      for i:=1 to m do  20      begin  21         read(l,r);  22         writeln(f[l,r]);  23      end;  24 end.

 

转载于:https://www.cnblogs.com/wuminyan/p/4743391.html

你可能感兴趣的文章
python爬虫之图片下载APP 2.0
查看>>
SparkSQL自适应执行
查看>>
python setup.py bdist_wheel 报错的处理办法
查看>>
JS简单实现决策树(ID3算法)
查看>>
Vue 组件库 heyui@1.18.0 发布,新增地址选择、图片预览组件
查看>>
GitHub 宣布私有库免费,最多可3人协作
查看>>
分库分表的正确姿势,你GET到了么?
查看>>
人工智能相关职位数据分析-需求分析
查看>>
SAP成都研究院许聚龙:Hello, Coresystems!(下)
查看>>
SEO快排之深刻教训,快速排名如何做更好
查看>>
AIOps 会抢走你的工作吗?
查看>>
给一句 SQL 就能做多维分析
查看>>
谈谈英国的移动支付和“虚拟银行卡”
查看>>
一周前,一群有才华有“钱途”的人做了一件可能改变未来的事
查看>>
Android常见错误汇总
查看>>
计算与Plumbing Work
查看>>
如何通过审计安全事件日志检测密码喷洒(Password Spraying)攻击
查看>>
JDK 12 公布首个 JEP ,你的迁移计划提上日程了没?
查看>>
为什么国内程序员更喜欢用国外技术网站?
查看>>
5天赚十亿!纯C/C++打造“西虹市首富”
查看>>