[LightOJ - 1289] LCM from 1 to n
[LightOJ - 1289] LCM from 1 to n 这篇文章以后的更新都会在 https://two-plus-two-make-four.blogspot.com/2020/01/lightoj-1289-lcm-from-1-to-n.html 题意 求 (1, 2, ..., n) 的 最小公倍数 (lcm) ，多组测试数据 一些想法 MicroMaker 神犇说是和 φ 函数有关的一些东西，但是想了半天似乎并没有什么思路 于是就有了一个很暴力的想法 其实还有一个更 naive 的想法，先把质数表跑出来，再预处理出每个质数的次方之类的信息，然后二分查找什么的，都扯到压缩数据了。。。 题解 先用线性筛把 1 ~ 1e8 的所有质数给筛出来 然后考虑这样一个客观事实（来自官方题解） lcm(1, 2, ..., n + 1) = lcm(1, 2, ..., n) * p 这里的 p 是指素数，如果 n + 1 = p ^ k ，那么就得到那样的递推式 lcm(1, 2, ..., n) 其它情况 有了递推式就好办了 接下来就到了喜闻乐见的 O(n) 过一亿 时间 看到 CSDN 上有人手写 bitset ，感觉自带的 bitset 效率也不错啊。。。 STL 依赖症患者 以下是丑陋的代码： # include "bits/stdc++.h" using namespace std ; typedef long long ll; typedef unsigned long long ull; template < typename Tp> inline void read (Tp &x) { x = 0 ; bool neg = 0 ; char c = getchar(); for...