博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【CH4302】Interval GCD
阅读量:5317 次
发布时间:2019-06-14

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

思路:线段树维护a的差分数组的gcd,

因为$gcd(a_1,a_2,a_3,...,a_n)=gcd(a_1,a_2-a_1,a_3-a_2,...,a_n-a_{n-1})$

原区间修改可以转化为差分数组上的两次单点修改。

因为实际计算时还需要原数,所以用树状数组维护b的增减量。

询问时,用这条语句即可:

printf("%lld\n",abs(gcd(a[L]+szszfuc::ask(L)/*左端的原数*/,segfuc::ask(1,L+1,R))/*其它差分的gcd*/));

 

注意:长时间测试不对,可以重写代码。

           PS:n,m不可混,要时刻看题。

 

转载于:https://www.cnblogs.com/xzs123456/p/10476173.html

你可能感兴趣的文章
[poj1006]Biorhythms
查看>>
Hyper-V虚拟机上安装一个图形界面的Linux系统
查看>>
Hover功能
查看>>
js千分位处理
查看>>
Mac---------三指拖移
查看>>
字符串类型的相互转换
查看>>
HTTP状态码
查看>>
iOS如何过滤掉文本中特殊字符
查看>>
基础学习:C#中float的取值范围和精度
查看>>
MongoDB-CRUD
查看>>
javaagent 简介
查看>>
python升级安装后的yum的修复
查看>>
Vim配置Node.js开发工具
查看>>
web前端面试题2017
查看>>
ELMAH——可插拔错误日志工具
查看>>
MySQL学习笔记(四)
查看>>
【Crash Course Psychology】2. Research & Experimentation笔记
查看>>
两数和
查看>>
移动设备和SharePoint 2013 - 第3部分:推送通知
查看>>
SOPC Builder中SystemID
查看>>