TZOJ 7548題解
描述：將一正整數的各個位數相加(即橫向相加)后，若加完后的值大于等于10的話，則繼續(xù)將各位數進行橫向相加直到其值小于十為止所得到的數，即為數根。換句話說，數根是將一數字重復做其數字之和，直到其值小于十為止，則所得的值為該數的數根。例如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. 常見循環(huán)模式：當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()函數一定會超時。我們可以找一下這里面的規(guī)律。我們就來看一下0-10之間的階乘數：
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
我們發(fā)現，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")
