I've solved this problem using DP.
Hint: The maximum sum of numbers for required sequence does not exceed 1568617.

Yea, precalc actually does work. I had an ineffecient solution which spent ~30 seconds and ~65 MB, so then i tried to precalc, but my initial variant didn't pass because it was 204kb of code, and the limit of 64kb is suddenly back (i don't recall it from before...)
In the end, i finally managed to compress it down to 63kb, due to the fact that out of 100k values, certain four numbers were present in 80%+ cases.

java  0.156 | 45 000 КБ

precalc)

100000 char's to 64K

Единица считается делителем