Существует ли целое число A такое, что оно имеет ровно X положительных целочисленных делителей и ровно K из них являются простыми числами?

Question

Мне нужно определить, существует ли целое число A такое, что оно имеет ровно X положительных целочисленных делителей и ровно K из них являются простыми числами. Нам дадут T тестовых случаев.

например, T = 1, X = 4 и K = 2

Then we get A = 6 which has exactly 4 factors: 1, 2, 3 and 6.
Exactly 2 of them are prime: 2, 3

Ограничения:

1 ≤ T ≤ 10 ^ 3

1 ≤ X, K ≤ 10 ^ 9

Поскольку ограничения X и K очень большие, проверка методом грубой силы работать не будет .

Answer 1

Задавая этот вопрос здесь, вы нарушаете кодекс поведения Codechef, поскольку это постановка проблемы из живого конкурса «April Long Challenge». Вот ссылка на эту проблему Пожалуйста, не задавайте такие вопросы до окончания живого конкурса.

Answer 2

Этот вопрос является частью текущего Codechef April Long Challenge 2020 . Ссылка на вопрос: [Question ] [1] И, следовательно, его не следует задавать непосредственно на этом портале. Это нарушает Кодекс поведения Codechef, и Codechef может запретить его использование. В будущем, пожалуйста, избегайте задавать вопросы в рамках продолжающегося соревнования по кодированию.