如何计算仅由数字1组成的最小倍数？

Question

我给出的数字k在1到10000的范围内.问题是找到只能用数字1写的最小倍数(称为repunit).因此,对于k = 3,解是111,因为3除以111,但是3不除1或11.对于k = 7,解是111111(六个).

如何计算任何k的解？

我知道我需要使用余数,因为解决方案可能非常大(或者我想使用BigInteger类)

Answer 1

这个问题涉及一些数学,所以让我们从它开始.

1111 ... 1(n数字1)=

.

让我们用随机数表示我们的随机数k.因为我们的条件是

,

它遵循

要么

,

哪里 表示同余运算符.我们正在寻找最小的这个n,这正是一个乘法的顺序.当且仅当10且9k相对为素数时,存在乘法顺序,这很容易检查.这里可以找到有效计算乘法顺序的一个例子,如果你不需要优化版本,那么基本的模幂运算可以解决这个问题:

int modexp(long mod) // mod = 9*k
{            
    int counter = 1;
    long result = 10;            
    while(result != 1)
    {
        result = (result * 10) % mod;
        counter++;
    }

    return counter;
}

额外:此功能保证在大多数phi(mod)时间运行,其中phi(mod)是Euler totient功能.此函数的重要属性是phi(mod) < mod,乘法顺序除以phi(mod).

Answer 2

如果你总能保证一个解决方案(至少是偶数n和倍数5,没有解决方案.我没有给别人太多考虑,但我认为其余的应该总是有一个解决方案):

(a + b) % c = ((a % c) + (b % c)) % c
(a * b) % c = ((a % c) * (b % c)) % c

%模运算符在哪里:a % b = the remainder of the division of a by b.这意味着我们可以在加法和乘法之间取模,这将有助于解决这个问题.

使用此方法,您可以使用以下算法,该算法在结果的位数上是线性的并使用O(1)内存:

number_of_ones = 1
remainder = 1 % n
while remainder != 0:
  ++number_of_ones

  # here we add another 1 to the result,
  # but we only store the result's value mod n.
  # When this is 0, that is our solution.
  remainder = (remainder * 10 + 1) % n

print 1 number_of_ones times

后续问题:如果你能使用0和1怎么办？