Ones

题目描述

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

#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;
}

真的太简单了!

《Ones》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>