求助一道题

学术版

Deuteron @ 2024-07-03 19:20:25

rt，定义 f(l,r)=\sum_{i=1}^l \sum_{j=l+1}^n \gcd(a_l,a_{l+1},\dots,a_r) 多次询问 f(l,r) 能做到什么复杂度，a_i 与 n 同级。

只会 O(n \sqrt n \log_2^2 n) 。

by Deuteron @ 2024-07-03 19:20:59

@Deuteron \gcd(a_i,a_{i+1},\dots,a_j)

by 红黑树 @ 2024-07-03 19:23:42

这么深刻。

by 红黑树 @ 2024-07-03 19:25:43

你的 r 没用吗？j 是不是从 r 开始枚举的。

by Deuteron @ 2024-07-03 19:28:01

@Deuteron \sum_{i=l}^r \sum_{j=i}^r \gcd(a_i,a_{i+1},\dots a_j)

by irris @ 2024-07-03 19:29:50

线段树历史版本和吧。

by critnos @ 2024-07-03 19:31:22

P9335

by 喵仔牛奶 @ 2024-07-03 19:43:54

@Deuteron 可以做到 \mathcal{O}(n\log v+q)。

见 P8421。

by panchunlin123 @ 2024-07-03 21:17:37



P9335和P8421，练去！
















































# ~~~~（~~~~选择排序！！！~~~~）~~~~