任意给定一个正整数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);
}
}
