Yet Another Hello World

tahsin_protik Replay of Ada Lovelace Na...

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 MM.

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,106][1, 10^6] in O(Rangelog(Range))O(Range * log(Range)).

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

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

Contributors

Statistics

83% Solution Ratio
naeem4265Earliest, Nov '21
Mushfiqur05Fastest, 0.1s
AlfehsaniLightest, 11 MB
FrdhsnShortest, 411B
Toph uses cookies. By continuing you agree to our Cookie Policy.