95 lines
2.9 KiB
Java
95 lines
2.9 KiB
Java
import java.math.BigInteger;
|
|
import java.util.ArrayList;
|
|
import java.util.List;
|
|
|
|
// Title: Minimum positive multiple in base 10 using only 0 and 1
|
|
|
|
public class MinimumNumberOnlyZeroAndOne {
|
|
|
|
public static void main(String[] args) {
|
|
for ( int n : getTestCases() ) {
|
|
BigInteger result = getA004290(n);
|
|
System.out.printf("A004290(%d) = %s = %s * %s%n", n, result, n, result.divide(BigInteger.valueOf(n)));
|
|
}
|
|
}
|
|
|
|
private static List<Integer> getTestCases() {
|
|
List<Integer> testCases = new ArrayList<>();
|
|
for ( int i = 1 ; i <= 10 ; i++ ) {
|
|
testCases.add(i);
|
|
}
|
|
for ( int i = 95 ; i <= 105 ; i++ ) {
|
|
testCases.add(i);
|
|
}
|
|
for (int i : new int[] {297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878} ) {
|
|
testCases.add(i);
|
|
}
|
|
return testCases;
|
|
}
|
|
|
|
private static BigInteger getA004290(int n) {
|
|
if ( n == 1 ) {
|
|
return BigInteger.valueOf(1);
|
|
}
|
|
int[][] L = new int[n][n];
|
|
for ( int i = 2 ; i < n ; i++ ) {
|
|
L[0][i] = 0;
|
|
}
|
|
L[0][0] = 1;
|
|
L[0][1] = 1;
|
|
int m = 0;
|
|
BigInteger ten = BigInteger.valueOf(10);
|
|
BigInteger nBi = BigInteger.valueOf(n);
|
|
while ( true ) {
|
|
m++;
|
|
// if L[m-1, (-10^m) mod n] = 1 then break
|
|
if ( L[m-1][mod(ten.pow(m).negate(), nBi).intValue()] == 1 ) {
|
|
break;
|
|
}
|
|
L[m][0] = 1;
|
|
for ( int k = 1 ; k < n ; k++ ) {
|
|
//L[m][k] = Math.max(L[m-1][k], L[m-1][mod(k-pow(10,m), n)]);
|
|
L[m][k] = Math.max(L[m-1][k], L[m-1][mod(BigInteger.valueOf(k).subtract(ten.pow(m)), nBi).intValue()]);
|
|
}
|
|
|
|
}
|
|
//int r = pow(10,m);
|
|
//int k = mod(-pow(10,m), n);
|
|
BigInteger r = ten.pow(m);
|
|
BigInteger k = mod(r.negate(), nBi);
|
|
for ( int j = m-1 ; j >= 1 ; j-- ) {
|
|
if ( L[j-1][k.intValue()] == 0 ) {
|
|
//r = r + pow(10, j);
|
|
//k = mod(k-pow(10, j), n);
|
|
r = r.add(ten.pow(j));
|
|
k = mod(k.subtract(ten.pow(j)), nBi);
|
|
}
|
|
}
|
|
if ( k.compareTo(BigInteger.ONE) == 0 ) {
|
|
r = r.add(BigInteger.ONE);
|
|
}
|
|
return r;
|
|
}
|
|
|
|
private static BigInteger mod(BigInteger m, BigInteger n) {
|
|
BigInteger result = m.mod(n);
|
|
if ( result.compareTo(BigInteger.ZERO) < 0 ) {
|
|
result = result.add(n);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
@SuppressWarnings("unused")
|
|
private static int mod(int m, int n) {
|
|
int result = m % n;
|
|
if ( result < 0 ) {
|
|
result += n;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
@SuppressWarnings("unused")
|
|
private static int pow(int base, int exp) {
|
|
return (int) Math.pow(base, exp);
|
|
}
|
|
}
|