题解 |「LightOJ 1289」LCM from 1 to n
题解 |「LightOJ 1289」LCM from 1 to n
题意
求 \operatorname{lcm}(1,2,...,n) ，多组测试数据
题解
MicroMaker神犇说是和欧拉函数有关的一些东西，但是想了半天似乎并没有什么思路
于是就有了一个很暴力的想法
先用线性筛把 1\sim 10^8 的所有质数给筛出来
然后考虑如下性质：
若 n+1=p^k，其中 p 为质数，则 \operatorname{lcm}(1,2,...,n+1)=\operatorname{lcm}(1,2,...,n)\times p；
否则，\operatorname{lcm}(1,2,...,n+1)=\operatorname{lcm}(1,2,...,n)。
由于这题的时限是 4 秒，有了递推式就可以 O(n) 过一亿了。
