任意给定一个正整数N，求一个最小的正整数M（M>1），使得N*M的十进制表示形式里只含有1和0。

思路

• 求一个数 X，使得 X % N = 0 且 X 的十进制表示只含有1和0；
• 维护一个“余数数组”，对于从 0 ~ N-1 的每一个余数i，都有相应的最小 X, 满足 X % N = i；
• 填充余数数组，X = 10^k + Y, X % N = (10^k % N + Y % N) % N，直到找到余数为0对应的最小值。

参考代码

import java.math.BigInteger;

public class Solution{
    public BigInteger minRightInteger(int n) {
        BigInteger []remain2Num = new BigInteger[n];
        remain2Num[1] = new BigInteger("1");
        BigInteger base = new BigInteger("10"), N = new BigInteger(String.valueOf(n));
        for (BigInteger now = new BigInteger("10"); ; now = now.multiply(base)) {
            int remain = now.remainder(N).intValue();
            if(remain2Num[remain] == null){
                remain2Num[remain] = now;
            }
            for (int i = 1; i < n; i++) {
                if(remain2Num[i] == null)
                    continue;
                int newRemain = (remain + i) % n;
                if(remain2Num[newRemain] == null && remain2Num[i].compareTo(now) < 0){
                    remain2Num[newRemain] = now.add(remain2Num[i]);
                }
            }
            if (remain2Num[0] != null) break;
        }
        return remain2Num[0].divide(N);
    }
}