2

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

2017-03-03 提问

查看全部 4 个回答

13

使用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 这三个数即可。

推广链接