循环数

GitHub跳转原题关系图返回列表

逐个检查 1 到位数的乘积是否为原数字串的循环移位。

OJ: noi_openjudge

题目 ID: ch0113-06

难度:普及-

标签:字符串模拟高精度python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
    1. 复杂度
    2. 总结

题意

判断一个允许前导零的数字串是否为循环数：乘以 1 到位数的每个整数后，结果都应是原串的循环移位。

思路

原串的所有循环移位都恰好出现在 s + s 中。逐个计算乘积后用 zfill(length) 保留应有的前导零，检查其长度和是否为 s+s 的子串即可。Python 整数能直接处理本题 60 位数字。

代码

Python代码

python
number_string = input().strip()
number = int(number_string)
length = len(number_string)
doubled = number_string + number_string

for multiplier in range(1, length + 1):
    product = str(number * multiplier).zfill(length)
    if len(product) != length or product not in doubled:
        print(0)
        break
else:
    print(1)

复杂度

设位数为 nn，时间复杂度约为 O(n3)O(n^3)，空间复杂度为 O(n)O(n)。

总结

循环移位判定可转化为“是否出现在自身拼接串中”。