수학 솔루션 : 48

Question

질문 해커 순위에서, 나는 수학 솔루션을 원하는입니다 ...

시리즈의 마지막 10 개 자리를 찾기 ...

1^1 + 2^2 + 3^3 + ⋯ + N^N 

N이 너무 경우 큰 숫자

as where 1 <= N <= 2000000 

나는 N을 통해 반복되는 코드를 가지고 있지만 N> 1000000에 대해 완료하는 데 너무 많은 시간이 걸립니다.

시간을 단축하는 아이디어 ???

code: 
n = int(input()) 
if(n>=1 and n<=2*1e6): 
    s=0 
    for i in range(1, n+1): 
     s+=(i**i) 
    print(s%10000000000) 

Answer 1

이 코드는 파이썬과 유사하므로 사용중인 언어로 가정합니다 (사용중인 언어로 질문에 태그를 지정해야합니다).

큰 문제는 i**i이 엄청납니다. 그래서 파이썬은 모든 것을 추적하기 위해 큰 정수를 사용하고 있습니다. 2e6^(2e6)에는 12602060 자릿수가 있기 때문에 계산 속도가 너무 빠릅니다 (필요한 10 자리 이상). 이것은 또한 모듈러스를 루프 안으로 옮기는 제안이 도움이되지 않았 음을 의미합니다.

이 솔루션은 세부 Modular exponentiation를 참조하십시오 (누승을 복용하는 동안 계수를 취할 것입니다. 일부 구현 arehere. 당신이 (정수 오버 플로우에 대해 걱정할 필요가 없기 때문에 파이썬이 간단하게 사용 아이러니하게도하는, .) 원래 문제의 원인을

입니다 그러나 pow 당신이 선택 계수를 지정할 수 있기 때문에 파이썬이 더 쉽게 만들면서 당신이 당신의 원본 코드를 다시 작성할 수 있도록 :. 우리는 간단하게 할 수

n = int(input()) 
if (1<=n<=2e6): 
    s = 0 
    for i in range(1,n+1): 
    s += pow(i,i,10**10) 
    print(s%(10**10)) 

그러나 이 furthe 당신은 지능형리스트를 사용하고

n = int(input()) 
if (1<=n<=2e6): 
    s = sum(pow(i,i,10**10) for i in range(1,n+1)) 
    print(s%(10**10)) 

로 위를 다시 작성할 수 있도록 연구. 파이썬은 또한 sum 기능을 포함하지만 하나의 단계에 대한 변수를 할당하는 바보입니다. 그래서 당신은 당신이 파이썬에 대한 명령 줄 인터페이스를 사용하는 것을 선호하고,하지 않을 수 있습니다

n = int(input()) 
if (1<=n<=2e6): 
    print(sum(pow(i,i,10**10) for i in range(1,n+1)) % 10**10) 

하지만 입력을 체크 걱정 것을 다시 것 :

sum(pow(i,i,10**10) for i in range(1,2*10**6+1)) % 10**10