Problem 377

For the Sum of Digits Divisibility problem, there is a simple iterative approach that is easy enough to code up but too slow to use as a submission for the very large numbers in the test cases.

Without putting any solutions directly in the forum, I know there exists a way to calculate these solutions in O(1), but this also requires requires calculation of a "correction" factor. I can see that there exists a pattern to this correction factor, but I am not a genius mathematician to be able to calculate the correction factor directly from k.

Is there any chance to get help on the equation for at least how to generate the correction factor necessary to use the O(1) equation that solves the problem directly instead of using an iterative approach?

Thank you for any help, I did try not to give away any part of the problem in asking this question.

Yea, That's a good point. It might be fast "enough" to do the iteration to simply calculate this correction factor then plug it into the rest of the equation. I'll try that and see if the processing can complete in a reasonable time. Thanks.

I guess the pattern is more complex than I thought... Maybe I need to just do the simple iterative solution but in a language that is fast enough to complete for large numbers :-)

Ok... from getting the "expected" values back from a failed submission, I see there is another pattern that does not require doing any sequencing.