재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
고2 영어 4나옵니다 단어 같이 하면서 인강 들어보려하는데 신택스 사놓은게 있지만...
-
저는 국수영탐 2:4:1:3 정도 하는듯 지구 벼락치기한다고 물리 좀 유기했더니...
-
888888888아이고숨차888888888아이고숨차8888888
-
강기본 끝나고 하려는데요 뭐가 더 좋을까요?
-
대학원 가고싶당 6
석박통합 가야지
-
-
어떤 사람이 똥 마려운 강아지처럼 1시간에 네 번씩 왔다갔다 해서 총무가 보다못해...
-
발분 미드 제리부터 유럽식 꿀잼 진지 실력픽 도파민 터진다
-
문제에 대한 해설과 더 많은 무료 고난도 문제는 https://t.me/JerryEthic
-
파란 옥빛 구늘 꺼내 드는 은은한 소리가 들린다 이 부분 공감각 맞아요? 걍 구슬...
-
꿀모 시즌 2 3회 69
-
국어 맨날 5등급뜨는데 간당간당하게 나올때도 있고 잘나올때도 잇는데 그래봣자...
-
-
[속보] 머스크 "총기옹호 서명자 매일 1명 뽑아 14억원 준다" 10
일론 머스크 테슬라 최고경영자(CEO)가 미국 대선일까지 무작위 추첨을 통해 표현의...
재밌겠군
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이다.
옙옙