描述：將一正整數(shù)的各個位數(shù)相加(即橫向相加)后，若加完后的值大于等于10的話，則繼續(xù)將各位數(shù)進行橫向相加直到其值小于十為止所得到的數(shù)，即為數(shù)根。換句話說，數(shù)根是將一數(shù)字重復做其數(shù)字之和，直到其值小于十為止，則所得的值為該數(shù)的數(shù)根。例如54817的數(shù)根為7，因為5+4+8+1+7=25，25大于10則再加一次，2+5=7，7小于十，則7為54817的數(shù)根。

小明非常喜歡階乘和數(shù)根，當某數(shù)的階乘的數(shù)根和該數(shù)的數(shù)根相同，小明就會非常開心，稱這樣的數(shù)為開心數(shù)。小明想判斷輸入的整數(shù)是否為開心數(shù)。

輸入：

輸入有多組數(shù)據(jù)，每個數(shù)據(jù)都是一個整數(shù)。

對于30%的數(shù)據(jù)，數(shù)字不超過32767。

對于60%的數(shù)據(jù)，數(shù)字不超過2141483647。

對于90%的數(shù)據(jù)，數(shù)字不超過9223372036854775807。

對于100%的數(shù)據(jù)，數(shù)字位數(shù)不超過25位。

輸出：

如果是開心數(shù)，輸出“YES”，否則輸出“NO”。

樣例輸入：

5

6

樣例輸出：

NO

NO

提示：

第一個數(shù)：5! = 5 * 4 * 3 * 2 * 1 = 120，數(shù)根(5!) = 1 + (120 - 1) % 9 = 3，數(shù)根(5) =??1 + (5 - 1) % 9 = 5。

第二個數(shù)：6! = 6 * 5 * 4 * 3 * 2 * 1 = 720，數(shù)根(6!) =?1 + (720 - 1) % 9 = 9，數(shù)根(6) =??1 + (6 - 1) % 9 = 6。

數(shù)根(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()函數(shù)

print(math.factorial(10))

當然我個人是選擇第二種方法，而數(shù)根的公式則是1 + (n - 1) % 9，n為正整數(shù)。

所以一開始我想的代碼是這樣的：

# 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()函數(shù)一定會超時。我們可以找一下這里面的規(guī)律。我們就來看一下0-10之間的階乘數(shù)：

0! = 1

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120

6! = 720

7! = 5040

8! = 40320

9! = 362880

10! = 3628800

我們發(fā)現(xiàn)，6!的數(shù)根是1 + （720 - 1) % 9 = 9。同理計算可得digital_root(factorial(7)) = 9，digital_root(factorial(8)) = 9，digital_root(factorial(9)) = 9......

接下來每個數(shù)的階乘的數(shù)根都是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的倍數(shù)，其數(shù)根為3；凡是9的倍數(shù)，其數(shù)根為9。而只要是大于6以上的階乘，必然能被6!整除，當然也必然能被9整除。所以這道題就變成了判斷該數(shù)是否為9的倍數(shù)。

那么這道題的代碼可以寫成：

# Wrong Answer

from sys import stdin

for line in stdin:

? ? n = eval(line)

? ? if?1 +?(n - 1) % 9 ==?9:

? ? ? ? print("YES")

? ? else:

? ? ? ? print("NO")

但是這里面有一些特殊數(shù)據(jù)，例如0! = 1，而0是9的倍數(shù)，所以這里要更改。加個條件即可

1! = 1

2! = 2

這兩數(shù)的階乘和這兩數(shù)相同，其數(shù)根相同，所以要輸出“YES”

所以程序應該改為：輸入0為“NO”，輸入1或者2為“YES”，輸入3以上的數(shù)字則判斷該書是否為9的倍數(shù)，如果是則輸出“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")