First of all, you count, not show hits .
It is very important. All you have to do is an efficient way to count the device. As John Bentley wrote in Programming Pearls: "Any method that believes that all permutations of letters for a word are doomed to failure." Actually, I tried in python, as soon as "i" hit 10 ^ 9, the system was already freezing. 1.5 g of memory was consumed. Not to mention 10 18. And that also tells us, quote Bentley again: "The definition of the problem was about ninety percent of this battle."
And to solve this problem, I do not see the way without dynamic programming (dp). In fact, most of these ridiculously huge Euler issues require some kind of dp. The theory of dp itself is quite academic and dry, but realizing the idea of dp to solve real problems is not, in fact, a fun and colorful practice.
One solution to the problem is that we go from 0-9, then 10-99, then 100-999, etc. and extract the signatures of the numbers, sum the numbers with the same signature and process all of them as part, thus saving space and time.
Observation: 3 * 137 = 411 and 13 * 137 = 1781. Let me break the first result of “411” into two parts: the first two digits of “41” and the last digit of “1”. "1" remains, but the "41" part will be "transferred" to further calculations. Let me call the "41" carry, the first element of the signature. "1" will remain as the rightmost digit in the calculation of 13 * 137, 23 * 137, 33 * 137 or 43 * 137. All these * 3 numbers have a "3" as their right digit, and the last digit 137 * n is always 1. That there is a difference between these "3" and "1" is +2, let's call it +2 "diff" as the second element of the signature.
OK, if we find a two-digit number with 3 as the last digit, we need to find the digit "m" that satisfies
diff_of_digitsum (m, 137*m+carry) = -2 (1)
to neutralize our +2 diff accumulated earlier. If m can do this, then you know m * 10 + 3, on the paper you write: "m3" is a hit.
For example, in our case, we tried the number 1. diff_of_digitsum (digit, 137 * digit + carry) = diff_of_digitsum (1, 137 * 1 + 41) = -15. Which is not -2, so 13 is not a hit.
Let see 99. 9 * 137 = 1233. "diff" is 9 - 3 = +6. "Carry" is 123. At the second iteration, when we try to add the number 9-9 and make it 99, we have diff_of_digitsum (digit, 137 * digit + carry) = diff_of_digitsum (9, 137 * 9 + 123) = diff_of_digitsum (9 , 1356) = -6 and neutralizes our surplus 6. Thus, 99 is a hit!
In the code, we just need 18 iterations. In the first round, we are dealing with single digits, the 2nd circle with 2-digit numbers, then 3-digit numbers ... until we get 18-digit numbers. Make a table before iterations with a structure like this:
table[(diff, carry)] = amount_of_numbers_with_the_same_diff_and_carry
Then the iteration begins, you need to constantly update the table when you go. Add new entries if you encounter a new signature and are always updating amount_of_numbers_with_the_same_diff_and_carry. Round one, single digits, fill out the table:
0: 0 * 137 = 0, diff: 0; carry: 0. table [(0, 0)] = 1
1: 1 * 137 = 137. diff: 1 - 7 = -6; carry: 13. table [(- 6, 13)] = 1
2: 2 * 137 = 274. diff: 2 - 7 = -5; hyphenation: 27. table [(- 5, 27)] = 1
Etc.
The second iteration, “10th digit”, we go over the number 0-9 as “m” and use it in (1) to see if it can create a result that neutralizes the “diff”. If so, then this m will do all of these amount_of_numbers_with_the_same_diff_and_carry in hits. Therefore, the count is not shown. And then we can calculate the new diff and transfer with the added digit, as in example 9 has diff 6 and carries 123, but 99 has diff 9 - 6 (the last digit from 1356) = 3 and carry 135, replace the old table using the new information.
Last comment, be careful with the number 0. It will appear many times in the iteration and not re-read it, because 0009 = 009 = 09 = 9. If you use C ++, make sure the sum is unsigned long and such, because that he is big. Good luck.