Factovisors

시간 제한1초메모리 제한128 MB

요약
여러 쌍의 n과 m이 주어질 때 m이 n!을 나누는지 소인수 분해로 판정한다.
난이도

보통10점 중 5점

유형
정수론, 수학
정답자
아직 제출이 없습니다

문제

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

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

정수 kk가 존재하여 k×a=bk \times a = b를 만족하면, aa가 bb를 나눈다고 합니다.

두 음이 아닌 정수 nn과 mm이 주어질 때, mm이 n!n!을 나누는지 판별하세요.

입력

입력은 여러 줄로 이루어지며, 각 줄에는 두 개의 음이 아닌 정수 nn과 mm이 공백으로 구분되어 주어집니다. 두 정수 모두 2312^{31}보다 작습니다. 입력은 파일의 끝(EOF)까지 계속됩니다.

출력

각 입력 줄에 대해, mm이 n!n!을 나누면 m divides n!을, 나누지 않으면 m does not divide n!을 한 줄에 출력합니다. 여기서 m과 n은 입력으로 주어진 실제 값으로 바꿔서 출력합니다.

예제1

  1. 예제 1

    입력
    6 9
6 27
20 10000
20 100000
1000 1009
    예상 출력
    9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!