kth990303의 코딩 블로그

문제는 아래와 같다. https://www.acmicpc.net/problem/8112 8112번: 0과 1 - 2 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수 중에서 가장 작은 수를 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 요약하자면, 100만 이하의 자연수 N의 배수 중 가장 작은 0과 1로만 이루어진 수를 출력하라는 문제이다. 단, 시작숫자는 0일 수 없다. 의식의 흐름 및 해설 모든 자연수의 배수는 0과 1로 표시할 수 있다는 점을 알고 있으면 좋다. 이산수학 시간에 배운다고 하는데, ps 덕분에 이산수학을 예습한 느낌 ㅎ... 아무튼 위 성질은 비둘기집의 원리로 증명할 수 있다. 자연수의 모든 배수는 0과 1로만 이루어진다는 것을..

문제 https://www.acmicpc.net/problem/15897 15897번: 잘못 구현한 에라토스테네스의 체 성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너 www.acmicpc.net 꽤 어렵게 다가온 수학문제이다. N이 1e9이므로 O(N)은 시간초과가 발생한다. 어떻게 해결해야 할까? Harmonic Lemma (조화수열의 성질) 예시로 N=6인 경우를 들어보자. j의 값은 i의 값이 더해지므로, i의 값이 횟수에 영향을 준다. 맨 처음에 j는 디폴트값으로 1이므로, 1+(N-1)/i의 값이 횟수가 됨을 확인할 수 있다. 그러나, 아직까지는 아래 O(N) ..