백준/수학 (35) 썸네일형 리스트형 백준 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를 알지 못한다면 이 글을 참조하여 사용하면 된다. 백준 10728 - XOR삼형제 1 https://www.acmicpc.net/problem/10728 대회 에디토리얼에 의하면 이 문제는 백트래킹 사용을 염두에 두고 나온 것으로 보인다. 다만 백트래킹으로 문제를 푸는 것은 그다지 의미가 없다고 판단되어 제한이 더 큰 XOR삼형제 2에도 쓸 수 있는 솔루션을 동일하게 적용했다. 여기에서 확인할 수 있다. 백준 10736 - XOR삼형제 2 https://www.acmicpc.net/problem/10736 수열의 최대 길이 찾기 XOR의 성질에 따라 $V \oplus V = 0$ 이므로 XOR 과정 중 중복되는 수를 만나서는 안된다. 다시 말해 어떤 세 원소를 선택하든 최소 한 개의 비트를 살릴 수만 있으면 된다는 것이다. 그렇다면 100 이하의 수로 구성할 수 있는 수열의 최대 길이는 어떻게 찾을 수 있을까? 32와 64를 이진수로 나타낸 표를 보면서 생각해보자. X 1 0 0 0 0 0 1 0 0 0 0 0 0 이 표에 존재하는 0을 0 혹은 1로 채우는 경우의 수를 만든다고 했을 때 1이 절대로 들어가서는 안 되는 경우가 무엇일까? X 1 0 0 0 0 0 1 NO 0 0 0 0 0 바로 64에서 $2^{5}$에 해당하는 비트이다. .. 백준 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.. 백준 13172 - Σ https://www.acmicpc.net/problem/13172 문제 요약 $N_{i}, \: S_{i}$가 M개 주어지는데 이들을 $a \times (b^{-1} \mod p)$ (p는 소수)의 형태로 바꾸고 그 합의 모듈러를 구하라. 풀이 문제에서 페르마의 소정리를 사용하라고 했으므로 페르마의 소정리를 통해 $N_{i} \mod p$를 구한 뒤 $S_{i}$를 곱하면 된다. 문제의 이름처럼 기대값들을 모두 더하는 것을 잊지 말자. 전체 코드 더보기 #include using namespace std; using ll = long long; #define mod 1000000007 int m; ll pomod(ll val, int b) { if (b == 1) return val % mod; if .. 이전 1 2 3 4 5 6 7 다음
