网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P1890
2024-07-08
题解:洛谷 P1890 gcd区间
题解:洛谷P1890gcd区间标签:线段树,st表,分块,dp题意给定数列\(a\),有\(m\)次询问求区间\([l,r]\)的最大公约数。思路这道题有多种写法,如标签所示。线段树线段树可以维护具有结合性的操作,很明显\(\gcd\)满足。这道题线段树跑的慢是因为无修改操作,自然没有其他\(O(1)