[Project Euler] 29. 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b로 만들 수 있는 a^b의 개수

29. 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b로 만들 수 있는 a^b의 개수

2 ≤ a ≤ 5 이고 2 ≤ b ≤ 5인 두 정수 a, b로 만들 수 있는 ab의 모든 조합을 구하면 다음과 같습니다.


22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다.


4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
그러면, 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 ab는 중복을 제외하면 모두 몇 개입니까?

Click

brute-force로 하면 비효율적이긴 하지만 금방 구현할 수 있었을 텐데 좋은 방법 찾아본다고 고생을 했네요. 아무튼.... 결국 찾았습니다. 고생의 원인은 역시 사소한 실수....

2<=a<=n, 2<=b<=n 으로 만들 수 있는 숫자는 총 n-1개.

이 때 a^(b)가 이전에 구한 어떤 수 c^(d)과 중복이 된다면.
그 말은 a와 c 모두 어떠한 수 i의 제곱수라는 것이다.

이때 a = i^(t), c = i^(j) 라고 한다면. a^(b)와 c^(d)는 (i^(t))^(b) , (i^(j))^(d)가 되고.
이때 t*b, j*d가 같을때 중복이 됩니다.
즉. t,j의 공배수일때 중복이 된다는 것을 알 수 있습니다.

그리고 위에 두가지 내용을 가지고 구현할 것을 종합해 보면....

1. 100까지의 배열을 만들어 배수값들을 저장해 둔다.
2. 현재 값이 제곱으로 만들어 지는 수가 아닐 경우 sum에 n-1값을 더해준다.
3. 현재 값이 어떠한 수 k에 t제곱일 경우.    
    2부터 t까지 작은 수의 경우만 중복의 수를 판단하여 n-중복수를 sum에 더해준다.

3가지 단계에 의해 구현.

그리고 아래가 위에 알고리즘을 정리한 코드.

<script language="Javascript" type="text/javascript">
function euclid(a,b){
 if (b == 0) return a;
 return euclid(b, a % b);
}
/* 최대 공약수 */
function gcd(a,b){
 return euclid(Math.max(a,b),Math.min(a,b));
}
function p029(n){
   var sum = 0;
   var square = new Array();       //어떠한 수의 제곱값으로 나타낼 수 있는지를 저장하는 배열.
   for(var i=2; i<=n; i++){
      if(isNaN(square[i])){       //어떠한 수의 제곱값인지 판단.
         sum += n-1;
         var temp = i*i;
         for(var j=2; temp<=100; j++){   //현재 수의 제곱 값들을 배열에 저장.
            square[temp] = j;
            temp *= i;
         }
      }
      else{                     //어떠한 수의 제곱으로 나타내어지는 수의 경우.
         sum += n;
         var arr = new Array();      //중복을 판단하기 위한 배열.
         for(var j=1; j< square[i]; j++){
            var p = square[i] / gcd(square[i],j); //p 현재값을 만드는 지수 중 j지수와 공약수를 제외한 수.
            var q = j / gcd(square[i],j);   //q j지수 중 현재값을 만드는 지수와의 공약수를 제외한 수.
            var r = q;
            for(var k=p; k<=n; k+=p){               //k를 p씩 증가. 즉 두 지수 t,j의 공배수를 찾음.
               if(arr[r] != true){
                  sum--;
                  arr[r] = true;
               }
               r += q;
            }
         }
      }
   }
   return sum;
}
</script>