Very true, I have solved it in a weird manner but I still cannot get the proof.

Input

N = 64, K = 3

Output

7

This can be expressed as a product of three integers in the following ways:

1 x 1 x 64

1 x 2 x 32

1 x 4 x 16

1 x 8 x 8

2 x 2 x 16

2 x 4 x 8

4 x 4 x 4

Therefore, 7 ways.

Great approach. I thought one topological sort will work after adding all the edges. But your approach looks like to be correct.

N is up to 1e9. Can we use prime factors of N to solve this?

Can you share your implementation? There are lot's of doubt over it.

Got AC, thanks for the intuition.

Great explanation, but I believe it may not produce correct output when P == Q.

In editorial TROY Query, Because when the answer to a query is No, the answer to the next queries will be also No. Can someone explain me why?