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.
Codeforces Round #322 (Div. 2)
Contest Problems / Contest ResultA. Vasya the Hipster빨간 양말의 개수 a와 파란 양말의 개수 b가 주어졌을 때, 서로 다른 색으로 짝을 지을 수 있는 최대 양말 쌍의 개수와 그렇게 쌍을 지은 양말을 제외하고, 한 가지 양말 색깔만으로 만들 수 있는 양말 쌍의 개수를 출력하는 문제이다.전자는 min(a, b)이고 후자는 (max(a, b)-min(a,b))/2이다.#include #include using namespace std; int main() { int a, b; scanf("%d%d", &a, &b); int c = a; if (c > b) c = b; printf("%d ", c); a -= c; b -= c; printf("%d", max(a / 2..
2015. 9. 28.
