TZOJ 7548题解
描述：将一正整数的各个位数相加(即横向相加)后，若加完后的值大于等于10的话，则继续将各位数进行横向相加直到其值小于十为止所得到的数，即为数根。换句话说，数根是将一数字重复做其数字之和，直到其值小于十为止，则所得的值为该数的数根。例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于十，则7为54817的数根。
小明非常喜欢阶乘和数根，当某数的阶乘的数根和该数的数根相同，小明就会非常开心，称这样的数为开心数。小明想判断输入的整数是否为开心数。
输入：
输入有多组数据，每个数据都是一个整数。
对于30%的数据，数字不超过32767。
对于60%的数据，数字不超过2141483647。
对于90%的数据，数字不超过9223372036854775807。
对于100%的数据，数字位数不超过25位。
输出：
如果是开心数，输出“YES”，否则输出“NO”。
样例输入：
5
6
样例输出：
NO
NO
提示：
第一个数：5! = 5 * 4 * 3 * 2 * 1 = 120，数根(5!) = 1 + (120 - 1) % 9 = 3，数根(5) = 1 + (5 - 1) % 9 = 5。
第二个数：6! = 6 * 5 * 4 * 3 * 2 * 1 = 720，数根(6!) = 1 + (720 - 1) % 9 = 9，数根(6) = 1 + (6 - 1) % 9 = 6。
数根(0) = 0。
首先，阶乘的计算方式可以这么算：
1. 常见循环模式：当n = 10时
n = 10
res = 1
for i in range(1, n + 1):
res = res * i
print(res)
2. 使用math模块里的factorial()函数
print(math.factorial(10))
当然我个人是选择第二种方法，而数根的公式则是1 + (n - 1) % 9，n为正整数。
所以一开始我想的代码是这样的：
# Time Limit Exceeded
from sys import stdin
from math import factorial
for line in stdin:
n = eval(line)
if 1 + (n - 1) % 9 == 1 + (factorial(n) - 1) % 9:
print("YES")
else:
print("NO")
但是这里的n非常大，如果直接使用factorial()函数一定会超时。我们可以找一下这里面的规律。我们就来看一下0-10之间的阶乘数：
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
我们发现，6!的数根是1 + （720 - 1) % 9 = 9。同理计算可得digital_root(factorial(7)) = 9，digital_root(factorial(8)) = 9，digital_root(factorial(9)) = 9......
接下来每个数的阶乘的数根都是9。这是因为6! = 1 * 2 * 3 * 4 * 5 * 6 = 1 * 2 * 3 * 4 * 5 * (2 * 3) = 1 * 2 * (3 * 3) * 4 * 5 * 2，其中3 * 3 = 9，我们知道，凡是3的倍数，其数根为3；凡是9的倍数，其数根为9。而只要是大于6以上的阶乘，必然能被6!整除，当然也必然能被9整除。所以这道题就变成了判断该数是否为9的倍数。
那么这道题的代码可以写成：
# Wrong Answer
from sys import stdin
for line in stdin:
n = eval(line)
if 1 + (n - 1) % 9 == 9:
print("YES")
else:
print("NO")
但是这里面有一些特殊数据，例如0! = 1，而0是9的倍数，所以这里要更改。加个条件即可
1! = 1
2! = 2
这两数的阶乘和这两数相同，其数根相同，所以要输出“YES”
所以程序应该改为：输入0为“NO”，输入1或者2为“YES”，输入3以上的数字则判断该书是否为9的倍数，如果是则输出“YES”，否则输出“NO”。
# Accepted
from sys import stdin
for line in stdin:
n = eval(line)
if n == 0:
print("NO")
elif n == 1 or n == 2 or 1 + (n - 1) % 9 == 9:
print("YES")
else:
print("NO")
