정수론14 재밌는 문제 - [조합/정수론] 2023 인하대 의대논술 3번문제이다. 정수, 확률, 논리를 잘 물어보는 문항이다. 경시나 논술에 자주 나오는 나머지관찰(mod)이나 귀류법 증명등 유명한 접근법이 쓰였다. mod식 서술은 고등범위가 아니므로 서술하는데 꽤 까다롭다. 3-1, 3-2 a) 풀이) 더보기 3-2 (b) 풀이) 더보기 3-3 풀이) 더보기 2023. 11. 29. 2024 연세대 수리논술 2번 풀이) 더보기 2023. 11. 28. 2015 고등KMO 1번 (정수) 풀이) 더보기 \(x-2y=a , 1-2y=b\)라고 하자. 식을 정리하면 \(ab | a^2+b^2-2ab+2a\) 가 된다. 이제 \(a\)를 나누는 어떤 소수 \(p\)가 존재하여 최대지수가 홀수(\(2k+1\))이라 하자. \(p^{2k+1} | a | b^2\) 이므로, \(p^{k+1} | b\)이다. 따라서 \(p^{3k+2} | ab | a^2+b^2+2a\) 이고, \(p^{4k+2} | a^2\)이므로, \( p^{3k+2} | b^2+2a\) 이다. \(a=p^{2k+1}A , b=p^{k+1}B\)이라 하자. (단, \(gcd(p, A)=1\)이다.) $$ p^{3k+2} | p^{2k+1}(pB+2A) \to p^{k+1} | pB+2A $$ 따라서 \( p | p^{k+1} | .. 2023. 11. 15. BOJ 26092 https://www.acmicpc.net/problem/26092 26092번: 수학적인 최소 공통 조상 첫째 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. $(1\leq a,b\leq 10^{12})$ www.acmicpc.net 시간복잡도 훈련에 좋은 문제입니다. 관찰 1. \( n \)의 소인수를 모두 구하는데 걸리는 시간은 \(O(\sqrt{n})\) 입니다. 정수 \(a, b\)에 대해 \(n=ab\)라고 표현할 수 있습니다. 일반성을 잃지 않고 \(a\leq b\) 라고 두면, \(n = ab\geq a^2 \) 이므로 \(a\leq \sqrt{n} \) 이 됩니다. 즉, 두 곱으로 쪼갰을 때, 작은 수 \(a \)만 찾으면 나머지 수는 \(n/a \)로 결정됩니다. 관찰 2. 값.. 2022. 12. 25. 이전 1 2 3 4 다음
