Ones

分析：比较简单的方案是：依次用1，11，111，1111，……来尝试，直到某个数与输入的余数为0为止。当然，111……1可能非常大（实际上可达数千位之巨，比如8141对应的111……1有3486位），为此我们要使用自制的“大数”来运算。据此有方案一：<!--more-->

#include <iostream>
#include <vector>

using namespace std;

typedef vector<char> BigNumber;

inline BigNumber bignum(int n) {
  BigNumber r;
  while (n) {
    r.push_back(n % 10);
    n /= 10;
  }
  return r;
}

inline void shift_add(BigNumber & n, char d) {
  n.push_back(0);
  for (int i = n.size() - 2; i >= 0; i--) {
    n[i + 1] = n[i];
  }
  n[0] = d;
}

inline bool less_than(const BigNumber & op1, const BigNumber & op2) {
  bool r = false;
  if (op1.size() != op2.size()) {
    r = op1.size() < op2.size();
  }
  else {
    for (int i = op1.size() - 1; i >= 0; i--) {
      if (op1[i] != op2[i]) {
        r = op1[i] < op2[i];
        break;
      }
    }
  }
  return r;
}

inline void subtract(BigNumber & op1, const BigNumber & op2) {
  int borrow = 0;
  int i;
  for (i = 0; i < op2.size(); i++) {
    char d = op1[i] - op2[i] - borrow;
    if (d < 0) {
      d += 10;
      borrow = 1;
    }
    else
      borrow = 0;
    op1[i] = d;
  }
  for (i = op2.size(); i < op1.size(); i++) {
    char d = op1[i] - borrow;
    if (d < 0) {
      d += 10;
      borrow = 1;
    }
    else
      borrow = 0;
    op1[i] = d;
  }
  while (op1.size() && !op1.back())
    op1.pop_back();
}

inline BigNumber first(const BigNumber & n) {
  BigNumber r(n.size(), 1);
  if (n.back() > 1)
    r.push_back(1);
  return r;
}

inline void increase(BigNumber & n) {
  n.push_back(1);
}

bool mod(const BigNumber & op1, const BigNumber & op2) {
  BigNumber r;
  for (int i = op1.size() - 1; i >= 0; i--) {
    shift_add(r, op1[i]);
    while (!less_than(r, op2)) {
      subtract(r, op2);
    }
  }
  return r.size();
}

int length(int n) {
  BigNumber bn = bignum(n);
  BigNumber t = first(bn);
  while (mod(t, bn)) {
    increase(t);
  }
  return t.size();
}

int main() {
  int n;
  while (cin >> n) {
    cout << length(n) << endl;
  }
  return 0;
}

这么做正确性没有问题，但是会超时。关键在于mod运算的效率太低。如何改进？

设f(x)为x与a的余数：

f(x) = x mod a

其中x=111...1，0 < a < 10000。则：

f(10x + 1) = (10x + 1) mod a = ((10x) mod a + 1 mod a) mod a

= (((10 mod a)(x mod a)) mod a + 1 mod a) mod a

= (((10 mod a)f(x)) mod a + 1 mod a) mod a

当a > 10时有：

f(10x + 1) = ((10 * f(x)) mod a + 1) mod a

从此可见：

1）计算较大的x与a的余数可以利用较小的x与a的余数

2）在这个计算过程中只要使用int类型就可以保存任何变量的值（11...1除外，但它本身不需保存），因此可以使用编程语言本身的mod运算，极大地提高运算速度。

3）当a < 10时，手工计算可以得出（l(x)为1的个数）：

l(1) = 1, l(3) = 3, l(7) = 6, l(9) = 12

由此有方案二：

#include <iostream>
using namespace std;

char values[10] = {0, 1, 0, 3, 0, 0, 0, 6, 0, 9};

int length(int n) {
  int l;
  if (n > 10) {
    int r = 1;
    l = 1;
    while (r) {
      r = ((10 * r) % n + 1) % n;
      l++;
    }
  }
  else {
    l = values[n];
  }
  return l;
}

int main() {
  int n;
  while (cin >> n) {
    cout << length(n) << endl;
  }
  return 0;
}

真的太简单了！