当前位置: 首页 > news >正文

CF623B Array GCD

显然 gcd > 1 等价于枚举一个数,使得所有数都是这个数的倍数,进一步可以规约到枚举质因数。

如果确定了质因数,我们很好用 DP 做到 \(O(n)\) 的复杂度,但问题就是质因数的规模确实不小。

有一个结论是,只需要枚举 \(a_1, a_1 + 1, a_1 - 1, a_n, a_n + 1, a_n - 1\) 的质因数即可。

因为你发现,如果质因数不在这个里面,意味着它肯定要把 \(a_1, a_n\) 都删掉,这样就不符合只能删除长度 $ < n$ 的区间的规定,所以 \(a_1, a_n\) 必有一个数不会删掉,因此将规模缩小到 \(O(1)\) 级别,复杂度 \(O(n)\)

http://www.hskmm.com/?act=detail&tid=13114

相关文章:

  • Python爬虫实现双色球历史数据抓取
  • 酵母细胞工厂全球调控策略研究进展:从遗传编辑到智能响应
  • Avalonia 根据绑定的数据类型动态选择模板
  • PyTorch图神经网络(一)
  • Python版Sigstore稳定版发布:软件供应链签名新标准
  • 网速带宽概念
  • 跨网传输软件:打通数据孤岛,保障安全流通!
  • 「KDOI-07」能量场
  • 基于LQR控制器的柔性机械臂抑振
  • 202507_QQ_caidundun
  • 国内企业邓白氏编码免费申请流程
  • 在CodeBolcks下wxSmith的C++编程教程——wxSmith教程目录(序言)
  • 生命周期
  • CF1893D Colorful Constructive 题解
  • C#通过15位或者18位身份证判断性别年龄
  • 深入解析:​​XMedia Recode 全能视频音频转换与编辑工具
  • MySQL同步ES的 5 种方案
  • 如何支持高并发高吞吐量编程
  • outlook大附件发送是什么?
  • 好用的提示词
  • 202312_Dest0g3_StrageTraiffic
  • 2025年内外网文件传输新范式:十大好用的内外网文件摆渡系统
  • 双分布函数热 LBM 模拟二维封闭方腔自然对流
  • asp.net中的wwwroot是什么
  • 用光学计算加速AI模型中的卷积和矩阵乘法操作
  • 了解IWebHostEnvironment : IHostEnvironment
  • PDF24 Creator(完全免费多功能PDF工具箱) 易于使用 多语言支持 - 教程
  • 彩笔运维勇闯机器学习--lasso回归
  • IP地址的配置
  • 【2025-09-21】连岳摘抄