| 题目名称 | 2876. 区间最大公约数 |
|---|---|
| 输入输出 | interval_gcd.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 4 |
| 题目来源 |
 LGLJ
于2019-09-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：36， 通过率：36.11% | ||||
 梦那边的美好ET |
100 | 0.846 s | 36.55 MiB | C++ |
|
syzhaoss |
100 | 0.934 s | 55.62 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.998 s | 120.18 MiB | C++ |
 LGLJ |
100 | 1.023 s | 55.62 MiB | C++ |
 1020 |
100 | 1.027 s | 37.61 MiB | C++ |
 东条林荫 |
100 | 1.030 s | 67.07 MiB | C++ |
|
锝镆氪锂铽 |
100 | 1.093 s | 45.24 MiB | C++ |
|
锝镆氪锂铽 |
100 | 1.387 s | 45.24 MiB | C++ |
|
flyfree |
100 | 1.480 s | 43.05 MiB | C++ |
|
瑆の時間~無盡輪迴·林蔭 |
100 | 1.618 s | 67.07 MiB | C++ |
| 关于 区间最大公约数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
不能用负数和0的gcd！！！！！
| ||||
|
回复 @东条林荫 :
抓到你啦  斯内普和骑士
2020-12-04 22:57
3楼
| ||||
|
内存范围已修改，卡什么GCD线段树啊？
瑆の時間~無盡輪迴·林蔭
2020-10-14 12:15
2楼
| ||||
|
险些大小号一起身败名裂
东条林荫
2020-10-14 01:10
1楼
| ||||
【题目描述】
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
对于每个询问，输出一个整数表示答案。
【输入格式】
第一行两个整数N,M（N≤500000,M≤100000）。
第二行N个整数A[i]($-2^{60}\leq$ A[i]$\leq 2^{60}$)。
接下来M行表示M条指令，每条指令的格式如题目描述所示。
【输出格式】
对于每个询问，输出一个整数表示答案。
每个答案占一行。
【样例输入】
5 5 1 3 5 7 9 Q 1 5 C 1 5 1 Q 1 5 C 3 3 6 Q 2 4
【样例输出】
1 2 4
【来源】
《算法竞赛进阶指南》