求大神解算法，“编写程序，求n至少为多大时，n个1组成的整数能被2013 整除。”

Question

编写程序，求n至少为多大时，n个1组成的整数能被2013 整除。

Answer 1

使用python黑科技:

i = 1
while int('1' * i) % 2013:
    i += 1
print(i)

不使用黑科技:

i = s = t = 1

while s % 2013:
    i += 1
    t = t * 10 % 2013
    s = (s + t) % 2013
print(i)

而事实上可以从数论的角度看。

2013=3*11*61，故:

• 欲被3整除，n得是3的倍数

• 欲被11整除，n得是2的倍数

故 n 是 6 的倍数。

而n个1若被 61 整除，则n个9亦然。因为 61 和 10 互素，由费马小定理知 60 符合条件。故只须尝试 6，12，30 这三个数即可。

Answer 2

楼上已经有答案了，但私以为没有解释的很详细，因此才有此次回答。

首先，先列下本次回答的题纲:

• 代码解法(由于没有做要求，就用JS实现了)

• 数论解法(费马小定理)

代码解法

function getMinDividedNum(n) {
    var sum = 1,
    len = 1;
    while (sum % n) {
        len++;
        sum = (sum % n) * 10 + 1;
    }
    return len;
}

// 测试用例-注意，并不是所有数字都能输入，只能是素数或者由素数乘积组成的数
var num = 2013;
console.log('n:' + num + ',len:' + getMinDividedNum(num));
//输出:n:2013,len:60

代码详解

以上代码的核心其实就是判断1,11,111等N位数能否被n整除，也就是sum=sum*10+1。
但是考虑到最大值边界问题，于是将上述公式换为了
sum= (sum % n)*10+1

之所以能这样转换，是因为: (举例)

• 譬如判断 111是否能被3整除

• 可以是 (1*10+1)*10+1

• 也可以是判断

  • 第一步: 1%3=1 (1整除3的余数为1）

  • 第二步: 11%3=2 (11整除3的余数为2）

  • 第三步: 21%3=0 (符合条件)

• 换一个思路，假如判断(8+7)是否能被3整除，那么我们只需要现将它们能被3整除的部分去除调，用余数累加起来判断即可，也就是说只需要判断2+1能否被3整除即可

数论解法

费马小定理简介

首先得知道的是，费马小定理是欧拉定理的一种特殊情况，欧拉定理描述的是关于同余的性质，而费马定理如下:

假如a是整数，p是质数，且a，p互质(两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1

即a^(p-1)%p=1

费马小定理在本题中的应用

关键来了，本题与费马小定理有什么关系呢？

如上楼中有人提到，本题中，2013=3*11*61，所以需要满足

• 能被3整除

• 能被11整除

• 能被61整除

而前两者很容易就根据下面的条件判断出:

• 若一个整数的数字和能被3整除，则这个整数能被3整除。

• 若一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除。

因此马上就可以将条件转换为:

• n得是3的倍数(因为n个1加起来要是3的倍数)

• n得是2的倍数(奇位和偶数直接的差为0)

• 因此n是6的倍数

• n个1这个数(x)能被61整除

接下来就剩下了一个问题: n个1能被61整除，需要满足什么？接下来费马小定理就派得上用处了。

我们可以得知: 61和10互素。
所以套用上述的公式，可以得出: 10^(60)%61=1
所以:10^(60)-1=0 (mod 61)
而10^60 -1 就是60个9组成的数，也就是说 60个9组成的数能够被61整除。
那么自然60个1组成的数能够被61整除(因为61与3无关)，同时60又是6的倍数，因此满足条件。

更新，之前有不严谨之处
继续判断，60的符合条件的约数(6的倍数)有，6，12，30，60。
检查计算得出后可以知道只有60满足条件。

因此得出了结论: n至少为60时，n个1组成的数能够被2013整除

Answer 3

function sum($num,$int=1){
     $sum = 0;
     foreach (range(0,$num-1) as $key => $value) {
         $sum += $int*pow(10,$value);
     }
     return $sum;
}
$i=1;
while($i++) {
    if (sum($i) % 2013 == 0) {
        echo $i;//26
        break;
    }
    
}

Answer 4

var num = 2013;
var pow = Math.pow;
var floor = Math.floor;
var result = '';
var temp = 0;
var i = 0;
var flag = true;

while(flag){
  for (var n = 0; n < 10; n++) {
      if ((3 * n + (temp%10)) % 10 === 1) {
          result = n + result;
          temp = floor((num*result)/pow(10, i + 1));
          break;
      }
  }
  if(/1{3,4}/.test(temp.toString())){
    flag = false;
  }
  i++;
}

console.log(result);//55196776508251918087983661754153557432245956836120770547
console.log(result*2013);//1.1111111111111112e+59

跟楼上大神推理的结果一致，60个