[TopCoder,전체 탐색]재미있는 수학

1. 내가 짠 코드

import java.util.ArrayList;
public class test {
    public static void main(String[] args){
        test test = new test();
        int base = 9;
        int[] answer = test.digits(base);
        for(int i =0; i<answer.length;i++) {
            System.out.println(answer[i]);
        }
    }
    public int[] digits(int base){
        ArrayList<Integer> ans = new ArrayList<Integer>();
        for(int i = 2; i<base; i++){
            boolean ok = true;
            for(int k1 = 0; k1<base;k1++){
                for(int k2 = 0; k2<base;k2++){
                    for(int k3 =0; k3<base;k3++){
                        int num = k1+(k2*base)+(k3*base*base);
                        int sum = k1 + k2 + k3;
                        if((num%i==0)&&(sum%i!=0)){
                            //i의 배수이지만 각 자리수의 합이 i의 배수가 아니면
                            ok=false;
                            break;
                        }
                    }
                    if(!ok)
                        break;
                }
                if(!ok)
                    break;
            }
            if(ok) {
                ans.add(i);
            }
        }
        int[] answer = new int[ans.size()];
        for(int i=0;i<answer.length;i++){
            answer[i]= ans.get(i);
        }
        return answer;
    }
}
-------------------------결과---------------------------------
2
4
8
 

2. 개선 코드

 - 각 자리수의 합이 n으로 나누어 떨어지면 그 숫자도 n의 배수이다.

 - n진수가 주어졌을 때, (n-1)과 그의 약수가 답이다.

증명
n진수가 주어졌을 때
abc는 다음과 같이 나타낼 수 있다.
a*n^2+b*n+c
 
이 식은 다음과 같이 변환이 가능하다((n-1)에 관한 식으로 묶음)
(a(n-1)+(2a+b))(n-1)+a+b+c
 
따라서 a+b+c가 (n-1)의 배수라면 전체 식이 (n-1)의 배수가 됨.