Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 4월 17일 화요일

[Project Euler] 48. 11 + 22 + 33 + ... + 10001000 의 마지막 10자리

48. 11 + 22 + 33 + ... + 10001000 의 마지막 10자리
11 + 22 + 33 + ... + 1010 = 10405071317 입니다.

11 + 22 + 33 + ... + 10001000 의 마지막 10자리 숫자는 무엇입니까?
Click
오버플로우 처리만 한다면 간단한 문제.
마지막 10자리만 필요하다는 조건에서 오버플로우를 해결하는 방법이 보이네요. 

11자리 이상의 수는 아무런 영향을 미치지 않으니 계산을 할때 뒤의 10자리만 가지고 계산을 하면 됩니다. 식으로 표현하면 아래 처럼 된다는 군요.
(x + y) % m = ((x % m) + (y % m)) % m (x * y) % m = ((x % m) * (y % m)) % m
<script language="Javascript" type="text/javascript">
function p048(length){
    length ++;
    var mod = 10000000000;
    
    for(var i=1, sum = 0; i < length; i++){
        for(var j=1, pow = i; j < i; j++)
            pow = (pow*i)%mod;
        
        sum += pow;
    }

    alert(sum%mod);
}
</script>

댓글 없음:

댓글 쓰기