우수 답변
이전에이 질문에 대한 답변이 있었지만 찾을 수없는 것 같습니다. 이 답변에서 “처음부터”이 문제를 해결하려고 노력할 것입니다.
이 문제를 해결하는 방법에는 여러 가지가 있습니다. 먼저 30 개를 평가하세요. 그런 다음 일반적인 알고리즘을 사용합니다. 나머지가 0이 아닐 때까지 2로 나눕니다. 이것은 결국 답변으로 이어질 것이지만, 30! 33 자리 숫자이므로 시간이 걸립니다.
좋습니다. 다른 것을 시도해 보겠습니다. 6 \ cdot 8에서 2의 거듭 제곱은 무엇입니까? 음, 6 분의 2의 거듭 제곱 더하기 8 분의 2의 거듭 제곱, 즉 1 + 3 = 4입니다. 좋아요, 우리는 이것을 사용하여 우리의 답을 더 빨리 계산할 수 있습니다. 30 년부터! = 1 \ cdot 2 \ cdot 3 \ cdots 28 \ cdot 29 \ cdot 30, 우리는 숫자 1에서 30까지의 답을 더하여 답을 얻을 수 있습니다.
그것은 매우 빠르게 작동 할 것입니다. 1 분도 채 걸리지 않습니다. 그러나 우리는 더 잘할 수 있습니까? 물론 가능합니다! 더 빠른 접근 방식은 다음 사항에 주목하여 마지막을 개선 할 것입니다. 곱하는 숫자 (15)의 절반에는 2의 거듭 제곱이 하나 이상 포함되어 있습니다. 숫자의 1/4 (내림, 7)에는 적어도 2 개가 포함됩니다. 8 분의 1은 3을 포함합니다. 16 분의 1은 4를 포함합니다.
다시 말해서 숫자의 절반은 적어도 2의 제곱을 포함합니다. 그 중 절반은 2의 추가 거듭 제곱을 포함하고 나머지 절반은 추가로 포함됩니다. 우리의 질문에 대한 답은 15 + 7 + 3 + 1 = 26입니다.
마지막 말 : 우리가 어떻게해야하는지 명확해야합니다. 이를 유사한 문제로 일반화 할 수 있습니다. 여기서 소수 (이 문제에서는 2)를 다른 소수로 변경하거나 100!과 같은 더 큰 팩토리얼에 대해 묻는 경우. 예를 들어 100 분의 5의 힘! \ frac {100} {5} + \ frac {100} {25} = 20 + 4 = 24가됩니다.
답변
2의 거듭 제곱을 미세 조정해야합니다
이제 할 것입니다
= 30 / 2 + 30 / 2 ^ 2 + 30 / 2 ^ 3 + 30 / 2 ^ 4
= 15 + 7 + 3 + 1
= 26
그러므로 26은 2의 거듭 제곱입니다