Majid is a 3rd-grade elementary student and quite well in mathematics. Once, Majid's teacher asked him to calculate the sum of numbers 1 through n.
Majid quickly answered, and his teacher made him another challenge. He asked Majid to calculate the sum of the digits of numbers 1 through n.
Majid did finally find the solution. Now it is your turn, can you find a solution? Input
Two space-separated integers 0 <= a <= b <= 109.
Program terminates if a and b are -1. Output
The sum of the digits of numbers a through b. Example
Input: 1 10 100 777 -1 -1 Output: 46 8655
can anyone help me with this ?
It's dp problem. Let F(x) is the sum of digits of numbers 0 through x. answer = F(B) — F(A — 1). x = a[n — 1] * 10 ^ (n — 1) + ... + a[1] * 10 + a[0]. i.e. a[i] is i-th digit of number x. Let D(pos, digSum, constructedPrefixIsEqualToPrefixX) is answer to question "in how many ways we can put digits on positions 0, 1, ... pos, so the sum of digits is equal to digSum.
What is digSum ?
See this for sum of digit from 1 to N
misunderstood
It's 10^9. So you need a logarithmic solution.
i doubt it :3
http://pastebin.com/2jjauTrm