數論 - UVA 10139 - factovisors

UVA 10139 - factovisors

問題



n是一個大於等於0的整數，n!的定義如下：
0! = 1
n! = n * (n-1)!    for n>0
我們說 a 可以除 b 假如存在一個整數 k 使得
k*a=b

* 中文翻譯：Lucky 貓

Input

每一列測試資料有2個整數，n及m（0 <= n,m < 2³¹）。

Output

對每一測試資料，請輸出 m 是否可以除 n!。輸出格式請參考Sample Output。

Sample Input

6 9
6 27
20 10000
20 100000
1000 1009
5 0
0 1
0 2
1 0

Sample Output

9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!
0 does not divide 5!
1 divides 0!
2 does not divide 0!
0 does not divide 1!



解法
 github

計算每個質因數的次方數, 只要 n! 的每個質因數次方數 > m 的每個質因數次方數, 
就能整除