PKU 2649: Factovisors

Factovisors
Time Limit: 1000MS　　Memory Limit: 65536K
Total Submissions: 1620　　　Accepted: 431

Description

팩토리얼 함수 n!은 음이 아닌 정수에 대해 다음과 같이 정의됩니다

　　　0! = 1
　　　n! = n * (n-1)!　　(n > 0)


아래의 등식을 만족하는 정수 k가 존재하면 'a는 b를 나눈다'라고 말합니다

　　　k*a = b



Input

입력은 여러 줄로 구성되며, 각 줄은 두 개의 음이 아닌(그리고 2^31 미만의) 정수 n과 m을 포함합니다

Output

각 줄의 입력에 대해, 아래에 나온 것과 같은 형태로 m이 n!을 나누는지를 판별하여 한 줄에 출력합니다

Sample Input

6 9
6 27
20 10000
20 100000
1000 1009

Sample Output

9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!

Source

Waterloo local 1999.01.31


*역자 주
1. 입력이 여러 줄 들어올테니 EOF 처리 해주셔야합니다
2. 예시로 나온 입출력 외에 직접 케이스를 만들 경우, 입력과 출력 간의 m과 n의 순서가 반대이므로 헷갈릴 수 있습니다
3. 특정 케이스에 대해 처리하지 않으면 TLE를 빠져나올 수 없을겁니다