IM SORRY FOR MAKING THIS PROBLEM SO HARD :sob: :sob: :sob:

This problem can be simplified into the following math problem:

Find all ~p \leq X~ such that ~Np \equiv K \mod M~.

Subtask 1

It suffices to loop through all values from ~1~ to ~X~, inclusive, and to check if each one satisfies the modular equation.

Time Complexity: ~O(X)~

Space Complexity: ~O(1)~

Subtask 2

Since ~M~ is prime, there is exactly one solution to this modular equation.

The key to this subtask is to notice if ~Np \equiv K \mod M~, then ~N(p+Mq) \equiv K \mod M~, for ~q \in \mathbb{Z}~. The proof of this statement is left to the reader.

By doing so, it suffices to loop from ~1~ to ~M~ to find the solution of the equation. Then, since any solution is of the form ~p+Mq~, it is now a case of counting how many values of ~q~ are valid given than ~p+Mq \leq X~.

Time Complexity: ~O(M)~

Space Complexity: ~O(1)~

Additional Info

It is possible to solve this problem using modular inverse.

I cannot promise the next J4 will not be this bad...