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.
단축키
내 블로그
| 내 블로그 - 관리자 홈 전환 |
Q
Q
|
| 새 글 쓰기 |
W
W
|
블로그 게시글
| 글 수정 (권한 있는 경우) |
E
E
|
| 댓글 영역으로 이동 |
C
C
|
모든 영역
| 이 페이지의 URL 복사 |
S
S
|
| 맨 위로 이동 |
T
T
|
| 티스토리 홈 이동 |
H
H
|
| 단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.
