codeforces 703E Mishka and Divisors
2024-08-21 12:28:38
codeforces 703E Mishka and Divisors
题面
给出大小为\(1000\)的数组和一个数\(k\)，求长度最短的一个子序列使得子序列的元素之积是\(k\)的倍数，如果有多个解输出元素和最小的序列。
\(k\)和数组元素的数量级都是\(1e12\)。
题解
\(f[i][d]\)表示前\(i\)项是\(d\)的倍数的最优解。因为\(d\)只可能是\(k\)的因数，所以离散化一下\(k\)的因数即可。
过程中需要多次求\(gcd\)，直接求会超时。需要先预处理\(b[i]=gcd(a[i], k)\)，那么\(gcd(a[i], k/d) -> gcd(b[i], k/d)\)
最新文章
- Knockout.js随手记(8)
- WPF入门教程系列十九——ListView示例(一)
- Atitit.木马病毒自动启动-------------win7计划任务的管理
- 重新想象 Windows 8 Store Apps (47) - 多线程之线程同步: Semaphore, CountdownEvent, Barrier, ManualResetEvent, AutoResetEvent
- 文件 FIFO队列
- Python学习之eventlet.greenpool
- 转自 z55250825 的几篇关于FFT的博文（三）
- JS中简单的this学习
- RTC及sensor时间同步
- python dlib opencv 人脸68点特征检测
- java消息队列--ActiveMQ
- poj 3264 倍增 ST表
- 董事局主席董事长总裁首席执行官CEO总裁董事监事区别
- spring模拟ioc
- 标 题: JavaScript真的要一统江湖了
- mybatis forEach使用
- Linux下DNS服务器配置
- 避免Block中的强引用环
- Hibernate3.3.2_JUnit_BoforeClass不报异常的Bug处理
- 01.1 Windows环境下JDK安装与环境变量配置详细的图文教程