01047: Round and Round We Go

http://cs101.openjudge.cn/practice/01047/

A cyclic number is an integer n digits in length which, when multiplied by any integer from 1 to n, yields a"cycle"of the digits of the original number. That is, if you consider the number after the last digit to "wrap around"back to the first digit, the sequence of digits in both numbers will be the same, though they may start at different positions.For example, the number 142857 is cyclic, as illustrated by the following table: 142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142

输入

Write a program which will determine whether or not numbers are cyclic. The input file is a list of integers from 2 to 60 digits in length. (Note that preceding zeros should not be removed, they are considered part of the number and count in determining n. Thus, "01"is a two-digit number, distinct from "1" which is a one-digit number.)

输出

For each input integer, write a line in the output indicating whether or not it is cyclic.

样例输入

142857
142856
142858
01
0588235294117647

样例输出

142857 is cyclic
142856 is not cyclic
142858 is not cyclic
01 is not cyclic
0588235294117647 is cyclic

来源：Greater New York 2001

给一个整数，它的长度为n，从1开始一直到n和该整数相乘，判断每次结果是否和原来的整数是循环的。

# 24-物院-彭博
def generate_rotations(s):
    return {s[i:] + s[:i] for i in range(len(s))}


while True:
    try:
        n = input()
        length, num = len(n), int(n)
        rotations = generate_rotations(n)

        flag = True
        for i in range(2, length + 1):
            n_ = str(num * i)
            if n_ not in rotations and "0" + n_ not in rotations:
                flag = False
                break

        if flag:
            print(f"{n} is cyclic")
        else:
            print(f"{n} is not cyclic")

    except EOFError:
        break

系统的测试文件中数据有很多组，在程序里要写循环读取数据并判断是否读完文件的代码。Python模版这样写：

while(True):
	try:
    ...
	except EOFError:
    break

输入处理：使用 sys.stdin.read() 一次性读取所有输入数据，以提高效率。

# 24-物院-彭博
import sys
def generate_rotations(s):
    return {s[i:] + s[:i] for i in range(len(s))}

# 读取所有输入
input_data = sys.stdin.read().strip()
lines = input_data.split('\n')

for line in lines:
    length, num = len(line), int(line)
    rotations = generate_rotations(line)

    flag = True
    for i in range(2, length + 1):
        n_ = str(num * i)
        if n_ not in rotations and "0" + n_ not in rotations:
            flag = False
            break

    if flag:
        print(f"{line} is cyclic")
    else:
        print(f"{line} is not cyclic")

思路：大整数的乘法。

def calc(m, num):
    t = 0
    temp = [0] * len(num)
    for i in range(len(num)):
        temp[i] = (num[i] * m + t) % 10
        t = (num[i] * m + t) // 10
    
    # print(temp,t)
    if t > 0:
        return False
    return temp

'''
def judge(temp):
    n = len(temp)
    for i in range(n):
        k = 0
        # print(temp,num)
        if temp[i] == num[0]:
            while k < n and temp[(k + i) % n] == num[k]:
                k += 1

            if k == n:
                return True
    return False
'''

from collections import deque

def is_equal_with_rotation(lst1, lst2):
    deque1 = deque(lst1)
    deque2 = deque(lst2)
    for _ in range(len(lst1)):
        deque1.rotate(1)
        if deque1 == deque2:
            return True
    return False

while True:
    try:
        s = input()
        num = [int(digit) for digit in s]
        num.reverse()
        # print(num)

        flag = False
        for i in range(2, len(num) + 1):
            temp = calc(i, num)
            # print(temp)
            #if temp and not judge(temp):
            if temp and not is_equal_with_rotation(temp,num):
                print(s, "is not cyclic")
                flag = True
                break
            elif not temp:
                print(s, "is not cyclic")
                flag = True
                break
        if not flag:
            print(s, "is cyclic")
    except EOFError:
        break

王成睿 24物理学院：01047:Round and Round WeGo 这道题下面这种方法似乎有点问题？比如0909090909显然不是循环数但运行后输出是，而且奇怪的是提交后还AC了。是不是测试数据有点松。

https://blog.csdn.net/huanghuchuan/article/details/17879353 大意：输入一个长度为 2 to 60 的数值，判断其是否有周期性。周期性的定义根据题目中的描述。

思路： 判断n是否为周期数的方法：len为n的长度（根据题意，001 的长度为3），若满足 n*(len+1) = 9...9 (len个9) 并且 n+1 为素数时，n为周期数。

证明： 1/7 = 0.142857 142857 ..... 1/11 = 0.09090909.. 1/13 = 0.076923 076923 .....

规律为，当分母为素数时，所得结果都为循环小数。

以第一个式子 1/7 = 0.142857 142857 ..... 为例，因为后面小数的循环周期为6，所以不妨把它两边同时乘以 10^6 ， 所得新式子为： 10^6/7 = 142857.142857 142857 .... 又因为 1/7 = 0.142857 142857 ..... 所以在 10^6/7 = 142857.142857 142857 .... 的基础上给分子减去1， 就舍去了小数点后面的数值： 10^6/7 - 1/7 = 142857 化简得：（10^6-1）/7 = 142857 于是得到： 99999/7 = 142857 所以：142857 * 7 = 99999 成立。 因此可推出判断 n 是否有周期性的公式。

观察142857，我们用1至6的数来乘:

​ 1´ 142857=142857

​ 2´ 142857=285714

​ 3´ 142857=428571

​ 4´ 142857=571428

​ 5´ 142857=714285

​ 6´ 142857=857142

所得得结果是1、4、2、8、5、7六个数字依原来的次序循环排列只是开头的数字变动而已。这种数我们叫做循环数， 其实这个数142857是由1/7所形成循环小数的循环节(1/7=0.142857142857142857…)。 而所有循环数也都由某质数的倒数所形成之循环小数的循环节而得来的。下一个循环数是由质数17所形成的， 1/17=0.0588235294117647…，而0588235294117647即为一循环数(2*0588235294117647=1176470588235294)。

会产生如此循环数的质数依序为7、17、19、23、29、47、59、61、97(<100)。

142857还有一个很有趣的性质。当142857乘以7时其乘积为一连串的9(142857´ 7=999999)，而0588235294117647乘以17也是一连串的9。 还有142857分成两半相加也是一连串的9(注：142+857=999)，而0588235294117647分成两半相加: 05882352+ 94117647=99999999， 这真是非常奇妙的巧合。

def is_cyclic(num):
    """如果数字是循环数则返回True，否则返回False。"""
    return str(int(num) * (len(num) + 1)) == '9' * len(num)

numbers = []
while True:
    try:
        numbers.append(input())
    except:
        break
for num in numbers:
    if is_cyclic(num):
        print(f'{num} is cyclic')
    else:
        print(f'{num} is not cyclic')