Problem Solving/수학 썸네일형 리스트형 BOJ 1644 - 소수의 연속합 문제 링크https://www.acmicpc.net/problem/1644 문제 해결 1. 에라토스테네스의 체를 사용해서 소수들을 구하고 벡터에 삽입한다. 2. 소수들의 연속된 합이 되는 개수를 구한다. 주의할 점 || 생각해볼 점 1. 에라토스테네스의 체는 보통은 sqrt(N)만큼만 확인해서 소수임을 판별하는 데 사용하는 경우가 대부분인데, 이 문제에서는 sqrt(N)을 넘어가는 숫자들의 합으로 N이 될 수 있으므로, N만큼 확인해봐야한다. 2. N의 최대 범위가 4,000,000이고 소수의 개수는 2,831,461개가 된다. for문을 이중으로 사용하나 연속된 두 소수의 합이 N이 되거나 N을 초과하게 되므로 크게 문제될 것이 없다. 참고 - https://ko.wikipedia.org/wiki/%E.. 더보기 BOJ 13171 - A 문제 링크 https://www.acmicpc.net/problem/13171 문제 해결 1. Successive Squaring Method를 이용해서 문제를 해결해야한다. ( A와 X 모두 10^18이므로) 2. 문제에 해결 방법이 나와있는 쉬운 문제 주의할 점 || 생각해볼 점 1. 반드시 A도 나머지 연산을 해야한다. ( 곱하는 단계에서 오버플로우가 생길 수 있다.) 2. 곱하기 연산을 할 수도 있지만, 이진수로 표현함을 이용해서 비트 연산을 하는 것이 더욱 효율적이다. 참고 Successive Squaring Method : http://mathworld.wolfram.com/SuccessiveSquareMethod.html ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2436 - 공약수 문제 링크https://www.acmicpc.net/problem/2436 문제 해결1. 구하려는 두 수를 a, b로 놓는다. 2. a == (GCD*x), b == (GCD*y) 이므로, measure = x*y (x*y == LCM/GCD) 3. measure의 (x,y)쌍을 찾되 합이 가장 작은 것을 찾아야하므로 시간을 단축하기 위해, sqrt(measure)부터 찾는다. 주의할 점1. LCM == GCD*x*y가 성립하기 위해선 반드시 x와 y가 서로소임을 보여야한다. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 다음