재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
적절한거 고르는거에서 않은거 고르는건 위에 ox 하는걸로 좀 해결을 본거같은데...
-
무슨이론?
-
화작 82 미적 76 영어 2 사문 47 지구 41 이 정도면 대학 어느정도까지...
-
왜 문제되는거지 읽어보면 충분히 유해도서 지정된거 납득가는데 내 생각엔 이거에...
-
독서는 누가봐도 너무 빡세고 문학은 제한시간 이정도면 적당한건가요?
-
관계 유지를 위해 시간을 할애해야 한다는게 너무 스트레스 받을듯. 같은 이유로...
-
음성 피드백을 잘 고민해본다면...? 맞힐 수 있을 겁니다. 풀어보세요.
-
혹시 3등급까지 국영 좀 도와주실 분 계신가요...? 4
안녕하세요..! 문과이구요..! 화작 확통 영어 동사 사문 하고 있습니다. 국어랑...
-
지구덮 0
2번틀린거 진짜 개빡친다 50 가능햇는데… 지구 그럭저럭본거 말곤 진짜 다망한듯…...
-
나 8번 끝까지 붙잡고있었어도 못풀었는데 끝나자마자 자연수가 나를 반겨줘서 깨달음
-
10덮 유빈 0
이에 언제 올라오나요ㅠㅠㅠㅠ
-
취소했다가거는건 무효입니다 근데 이럼 아무도 안걸것같기도
-
수능 너무 고인것같음 10
중졸따리 개잼민이들이 보는 시험 난이도가 이게 맞음? 난이도는 전국에있는 수험생 다...
-
-
질서 정연한 사회의 장기목표는 무법국가와 마찬가지로 고통받는 사회를 질서 정연한...
-
일단 나는 취업,진로 등등 부차적인 이유들도 많겠지만 목적이 저거면 다른 길도 워낙...
-
그럼 난 보추 7
재밌겠군
18?
THANK(땡)
14?
정답!
증명은...?
6⁴ = 1296 < 2077 < 7⁴ = 2401 이므로
6⁴(1296), 5⁴(625), 4⁴(256), 3⁴(81), 2⁴(16), 1⁴(1)
위의 수들의 합으로 2077을 만들어야 함.
1⁴, 2⁴, ..., K⁴들의 합을 이용해 자연수 N을 만들 때
사용된 수들의 최소 개수 : a[N] 이라 하면
a[N] = if(N > i⁴)min(a[N], a[N - i⁴] + 1) (1 ≤ i ≤ K),
a[1⁴] = a[2⁴] = ... = a[K⁴] = 1 로 정의됨.
여기서 N = 2077, K = 6이므로
이를 c++ 코드로 잘 작성해서 돌려보면 a[2077] = 14가 나옴.
역추적까지 해보면
2×5⁴ + 4⁴ + 7×3⁴ + 4×1⁴ = 2077
임을 알 수 있음.
코드풀이는 좀;;
정수로 증명쉽게 되요 ㅋㅋ
풀면서 자꾸 다이나믹 프로그래밍 생각나길래 그만..저도 dp를 모르는게 아닙니다만..허허 수학은 손으로 풀어야된다고욥!
대충 sketch.
2077==13 (mod16)이고, x^4==0or1 (mod16)이므로 n은 최소 13이다.
옙옙