面白い数学

いや〜、進数変換は出来てるんですが、そこからがうまくいかない。解法が違うのだろうか・・・。全探索が未だに出来ていないという事実に押しつぶされてしまいそうです。（だがくじけない）これはもう、ひたすら全探索解いて頭に刷り込ませるしかないですね！！（白目）最初、ArrayList使えばメモリ節約出来るのでは・・・？と考えましたが、結局最後にint型配列に入れこむという処理が出てくるので、そのままやろうと考えました。ポジティブ思考で行こう！！俺は出来る！俺は出来る！！いけるぞ！！俺！

問題元：SRM150 Div2 Level2

public class Interesting {  

    public static int[] digits(int base) {
        int[] ret = new int[1000];
        for(int r = 1; r < 1000; r++) {
            int sum = 0, num = r;
            while(num != 0) {
                sum += num % base;
                num /= base;
            }
//          System.out.println("sum:" + sum); //DEBUG
            System.out.println("r:" + r + ", sum:" + sum);
            if(sum != 0 && sum != 1) {
                if(r % sum == 0)
                    ret[sum]++;
            }
        }
        return(ret);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        final int base = 10;

        int[] ans = digits(base);
        for(int r = 0; r < ans.length; r++) {
            if(ans[r] > 0)
                System.out.print(r + " ");
        }
    }
}

解決策１（４重ループによる全探索）

public static int[] digits(int base) {
        ArrayList<Integer> v = new ArrayList<Integer>();

        for(int n = 2; n < base; n++) {
            boolean ok = true;
            for(int k1 = 0; k1 < base; k1++) {
                for(int k2 = 0; k2 < base; k2++) {
                    for(int k3 = 0; k3 < base; k3++) {
                        if((k1 + k2* base + k3 * base * base) % n == 0 && (k1 + k2 + k3) % n != 0) {
                            //nの倍数の数で、各桁の和がnの倍数えなければ、このときのnは除外する
                            ok = false;
                            break;
                        }
                    }
                    if(!ok) break;
                }
                if(!ok) break;
            }
            if(!ok) v.add(n);
        }
        int[] ans = new int[v.size()];
        for(int r = 0; r < v.size(); r++) ans[r] = v.get(r);

        return(ans);
    }

解決策２（数式を用いて、処理を減らしたやり方）
数式：
a　× n^2 + b　× n^1 + c
a × (n - 1)^2 + (b - 2a) × (n - 1) + (a + b + c)
((a × (n - 1) + b - 2a) × (n - 1)) + (a + b + c)

public static int[] digits(int base) {
        Vector<Integer> v = new Vector<Integer>();

        for(int r = 2; r < base; r++) {
            if((base - 1) % r == 0) v.add(r);
        }
        int[] ans = new int[v.size()];
        for(int r = 0; r < v.size(); r++) {
            ans[r] = v.get(r);
        }
        return(ans);
    }