Yet Another Hello World

The problem wants the number of decryption system which doesn’t divide the encrypted message of a certain encryption system. It is easier to calculate the number of decryption system that divides the given encrypted message and then subtracts the result from $M$.

So, the problem is now to calculate the number of divisors of that encrypted message which is present in the set of the decryption systems. It can be calculated using “Sieve of Eratosthenes”. Firstly, calculate the frequency of each decryption system. Then while running the Sieve function, update the result according to its frequency. Thus, we can precalculate the results for the range $[1, 10^6]$ in $O(Range * log(Range))$.

Then there are $Q$ queries that can be answered using precalculated in $O(1)$.

The overall time complexity of the solution is $O(Q+Range* log(Range))$