Editorial | "LightOJ 1289" LCM from 1 to n

Problem statement backup

Problem

Find $\operatorname{lcm}(1,2,...,n)$, multiple test cases.

Editorial

MicroMaker, resident OI legend, reckoned it had something to do with Euler’s totient function, but I stared at it for a while and came up with nothing. So brute force it is.

First, use a linear sieve to sieve out all primes in $1\sim 10^8$. Then consider the following property:

If $n+1=p^k$, where $p$ is a prime, then $\operatorname{lcm}(1,2,...,n+1)=\operatorname{lcm}(1,2,...,n)\times p$; otherwise, $\operatorname{lcm}(1,2,...,n+1)=\operatorname{lcm}(1,2,...,n)$.

Since the time limit for this problem is $4$ seconds, once we have the recurrence we can push a hundred million through in $O(n)$.

Code backup