우수 답변
1의 표현에서! 200!까지 모든 숫자는 처음 6 개 항을 제외하고 14로 나눌 수 있습니다. 이유
- 14 = 2 \ times 7
- 이제 7은 6까지 없습니다!.
그러므로 R [\ dfrac {1! + 2! + 3! +… .. + 200!} {14}]
= R [\ frac {(1! + 2! +…. + 6!) + (7! + 8! +… .. + 200! )} {14}]
= R [\ frac {(1! + 2! +…. + 6!)} {14}] + R [\ frac {(7! + 8! + … .. + 200!)} {14}]
= R [\ dfrac {(1 + 2 + 6 + 24 + 120 + 720)} {14}] + 0
= R [\ dfrac {873} {14}]
= 5 ( 답변 )
답변
Quora에는 이런 종류의 질문이 많이 있습니다. 일반적으로 숙달하기 위해 심층적 인 통찰력이 필요하지 않습니다.
기억해야 할 주요 사항은 지수 화가 계수 아래에서 주기적이라는 것입니다. 우리는 그주기가 얼마나 큰지 알아 내기 만하면됩니다. 간단히 시도해 볼 수 있습니다.
2 ^ 1 = 2 2 ^ 2 = 4 2 ^ 3 = 8 2 ^ 4 = 16 ( 이 시점에서 우리는 16 = -1 모듈로 17이라는 것을 알아 차리고 멈추지 만 계속 진행하겠습니다. 2 ^ 5 = 32 = 15 2 ^ 6 = 2 * 15 = 30 = 13 2 ^ 7 = 2 * 13 = 26 = 9 2 ^ 8 = 2 * 9 = 18 = 1
이제 필요한 또 다른 사실은 x ^ {ab + c} = (x ^ a) ^ bx ^ c입니다. 2017 = 8 * 252 + 1, 2 ^ {2017} = (2 ^ 8) ^ {252} * 2. 위의 계산을 사용하면 2 ^ 8 = 1 mod 17이므로 2 ^ {2017} = 1 ^ {252} * 2 = 2 mod 17.
그런 다음 하나를 추가하여 최종 결과 인 3을 얻습니다.
답을 “직접”계산하고 싶다고 가정합니다. 반복 된 제곱을 사용하여이 작업을 수행합니다. 이는 모듈러스가 단일 사이클도 완료하지 못할만큼 충분히 클 수있는 응용 프로그램에 유용합니다. 이 기술의 기본은 x ^ {2k} = (x ^ k) ^ 2입니다. 이진수로 지수를 나타냅니다. 가장 왼쪽 이진수가 1 일 때마다 x를 곱합니다. 그런 다음 다음 숫자로 이동할 때마다 현재 값을 제곱합니다.
이 경우 2017 = 11111100001b입니다. 각 숫자를 차례로 취하고 (그리고 초기 값 “1”로 시작) :
1 : (1 * 2) ^ 2 = 4 1 : (4 * 2) ^ 2 = 13 mod 17 1 : (13 * 2) ^ 2 = 9 ^ 2 = 13 mod 17 1 : (13 * 2) ^ 2 = 13 1 : (13 * 2) ^ 2 = 130 : 13 ^ 2 = 16 0 : 16 ^ 2 = 1 0 : 1 ^ 2 = 1 0 : 1 ^ 2 = 1 1 : 1 * 2 = 2
이는 2 ^ {2017} = 2 mod 17이라는 이전 계산과 일치합니다.