BOJ 11690 LCM(1, 2, ... , n)
문제 링크자연수 n이 주어졌을 때, 1부터 n까지 모든 자연수의 최소공배수를 구하는 문제입니다.LCM(1, 2, ... , n) = LCM(1, LCM(2, ... , n)) = LCM(1, LCM(2, LCM(3, ... , n)))입니다.n 이하인 소수를 라 하고 그러한 소수가 총 m개라면, 답은 가 됩니다.n 이하인 소수를 모두 찾아야할텐데 당장 떠오르는 방법은 에라토스테네스의 체 입니다. 시간복잡도가 O(n lg lg n)이라 걱정은 되지만, 시간제한이 2초라서 아래와 같이 작성하였고 1556MS에 통과하였습니다.#include #include #include using namespace std;const long long mod = 4294967296;int n, p[6000005], pn;ch..
2015. 12. 4.
