Graph Theory, Dynamic Programming, GCD Properties, Number Theory, FFT
Its too big to be cited here. Please read the problem statement.
Key to AC- Reading the problem carefully is the key for making the crucial observations which would allow use of DP and FFT in the question. GCD properties also help.
Before starting the editorial, you are HIGHLY advised to read and practice these two problems in the tab below.
Once you are done with them, you’d realize that this problem is a very simple, or trivial extension of the intermixed concepts applied by them. Note that the solution uses the concept used by the best solution in WORDNINJ and hence can be slightly tricky to understand. Once you are done with these problems, you may refer to the tab below.
Your effort and intent to plagiarize in APRIL19 long is recorded (thanks to discourse giving names of users clicking links). Appropriate rating penalty and/or account ban will be applied in a few hours. We’d like to remind that codechef is committed in weeding out cheaters from the community who spoil the fun and decorum of the forums and also play against the contest spirit.
His lazy barbie doll hands are yet to write the code. Lol.
CHEF VIJJU’S CORNER
- TBD after looking at contestant’s solution