CF1538D Another Problem About Dividing Numbers

You are given two integers $ a $ and $ b $ . In one turn, you can do one of the following operations: - Take an integer $ c $ ( $ c > 1 $ and $ a $ should be divisible by $ c $ ) and replace $ a $ with $ \frac{a}{c} $ ; - Take an integer $ c $ ( $ c > 1 $ and $ b $ should be divisible by $ c $ ) and replace $ b $ with $ \frac{b}{c} $ . Your goal is to make $ a $ equal to $ b $ using exactly $ k $ turns. For example, the numbers $ a=36 $ and $ b=48 $ can be made equal in $ 4 $ moves: - $ c=6 $ , divide $ b $ by $ c $ $ \Rightarrow $ $ a=36 $ , $ b=8 $ ; - $ c=2 $ , divide $ a $ by $ c $ $ \Rightarrow $ $ a=18 $ , $ b=8 $ ; - $ c=9 $ , divide $ a $ by $ c $ $ \Rightarrow $ $ a=2 $ , $ b=8 $ ; - $ c=4 $ , divide $ b $ by $ c $ $ \Rightarrow $ $ a=2 $ , $ b=2 $ . For the given numbers $ a $ and $ b $ , determine whether it is possible to make them equal using exactly $ k $ turns.

N/A

N/A