정수론 (7) 썸네일형 리스트형 백준 12116 - Uzastopni https://www.acmicpc.net/problem/12116 힌트더보기$a$부터 연속된 $k$개의 정수의 합을 구하려면 다음과 같은 식으로 풀 수 있다. $a \times k + \frac{k \times (k - 1)}{2}$ 그 합이 $N$이 되려면 $N = a \times k + \frac {k \times (k - 1)}{2}$ 를 만족해야 함을 알 수 있다.풀이힌트에서 언급한 식 $N = a \times k + \frac{k \times (k - 1)}{2}$ 를 만족하는 $a$를 구해보도록 하자. 식을 정리하면 $2N = k(2a + k - 1) \rightarrow 2a = \frac{2N}{k} - k + 1$가 되므로 적절한 범위의 $k$에 대해 $2a$가 짝수인 경우를 모두 찾아.. 백준 14848 - 정수 게임 https://www.acmicpc.net/problem/14848 포함 배제의 원리를 이용해 집합에서 원소들을 지워나가는 문제이다. 단, 이 문제는 서로 배수 관계인 수가 있을 수 있으므로 원소들을 곱할 때 최소공배수를 계산해야 올바른 답을 얻을 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma") .. 백준 15965 - K번째 소수 필요 지식 이 문제는 소수 정리를 알면 매우 단순해진다. 풀이 소수 정리에 의해 ${e^{16} \over 16} \approx 555381$를 계산할 수 있고 $e^{16}$ 정도의 범위는 에라토스테네스의 체로 충분히 계산할 수 있음을 알 수 있다. 체를 돌려 50만번째 소수까지 찾아 출력하도록 하면 된다. 전체 코드 - 여기서는 linear sieve를 사용했다. 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma") #pragma.. 백준 16563 - 어려운 소인수분해 https://www.acmicpc.net/problem/16563 소인수 분해는 $O(\sqrt N)$의 시간 복잡도로 $\sqrt N$까지 반복문을 돌아 자연수를 나누는 방법이 가장 잘 알려져 있다. 하지만 이 문제는 소인수 분해를 해야 할 수의 개수가 $N \leq 10^{6}$이므로 이 방법을 사용하면 TLE 판정을 받게 된다. Linear sieve를 이용하여 소인수 분해를 $O(\log N)$에 할 수 있는 방법이 있다. Linear sieve를 사용하여 소수 목록을 $O(N)$에 구한 후 소인수 분해를 실시하면 1초 이하의 시간으로 AC를 받을 수 있다. Linear sieve를 알지 못한다면 이 글을 참조하여 사용하면 된다. 백준 4375 - 1 https://www.acmicpc.net/problem/4375 수 뒤에 계속 1을 붙여나가면서 배수가 성립하는지 확인하면 된다. 다만 이 과정에서 오버플로우가 발생할 수 있다. 큰 정수를 구현해서 풀 수도 있겠지만 1을 붙이면서 n으로 나눈 나머지만을 남겨 불필요한 부분을 제거하면 int 자료형을 이용하여 문제를 풀 수 있게 된다. 전체 코드 더보기 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; while (!cin.fail()) { int cnt = 1; int x = 1; while (x) { x %= n; if (!x) break; x *= 10; ++x; ++c.. 이전 1 2 다음
