Again, in case the servers are down, here are 14 examples plus answers. These are compiled into the main.cpp as examples 0 through 13. Also, if you give main.cpp two arguments it will treat them as S and X, so you can test your code that way too. If you get examples 0 through 13 correct and they are fast enough, you can be satisfied that you solved this problem.
| Number | S | X | Answer |
| 0 | 0 | 1 | 0 |
| 1 | 101 | 9 | 3 |
| 2 | 471 | 47 | 2 |
| 3 | 2222 | 97 | 5 |
| 4 | 95847362 | 436 | 216 |
| 5 | 102030405 | 85 | 316 |
| 6 | 8034151889109199226907 | 368249157 | 2582766 |
| 7 | 54019091675924410392006963001976 | 33857108 | 3685790257 |
| 8 | 949778566115406970397000000000000000000079641169 | 694874013 | 281455487794133 |
| 9 | 990450814731595674899314817951534213891202482671 | 777444111 | 241891551624992 |
| 10 | 906708300000000816661861190246822256891226113143 | 13879163 | 200119655333575 |
| 11 | 547371145238239979608276364147467162445006834154 | 26862 | 281474707766866 |
| 12 | 550000096205335065730009666579861000000769420768 | 75676722 | 213163063953684 |
| 13 | 957837542544882028114572037810101728066730780324 | 536624519 | 281469731899716 |
The tests.sh script tests these cases.
On the flip side, you can implement this enumeration pretty quickly, so it's not a bad idea to do so, so that you can double-check your answer later.
So, back to the drawing board.
long long comb(long long N, long long K); // Return N-choose-K.
class DigitStringDiv1 {
public:
long long count(string s, int x); // The topcoder problem.
int X; // The parameter X
string S; // The parameter S
string XS; // X as a string of digits
int SD; // Number of digits in S
int XD; // Number of digits in X
long long ngtr_digits(int sindex); // Counting strings whose sizes are > XD.
long long neq_digits(int sindex, int xindex); // Counting strings whose sizes are == XD
long long Cache[50][15]; // Memoization cache for neq_digits()
};
|
Your first job is to write comb() -- when you do this, do both the multiplication and the division in the same for loop. For example, if you're implementing 6-choose-3, you'll do the operations in the following order:
Test it, and the move onto ngtr_digits(). For this procedure, you want to count the number of strings that start with S[sindex] and that have more than XD digits. This is not a recursive procedure -- you can simply use comb() above to do that calculation.
Go ahead and test this one, too. It will get the correct answer for examples 0, 1 and 3. I'll give you another example to try, and put it into main.cpp as example 5:
S = "102030405"; X = 85; count(S, X) = 316; |
Now, the harder part -- to implement neq_digits(int sindex, int xindex). What this method does is return the number of strings, starting with S[sindex] that are the exact same size as XD-xindex and, when viewed as a number, are greater than atoi(XS.substr(xindex).c_str()). Let's use example 2 to illustrate. In this example, S is "471" and X is 47. So, let's break down the recursive calls of neq_digits():
S = "95847362"; X = 436; count(S, X) = 216; |
And here is the memoization cache:
sindex xindex neq_digits(sindex,xindex) ------ ------ ------------------------- 0 0 21 1 0 15 2 0 10 3 0 4 4 0 3 4 1 3 5 0 0 5 1 0 6 0 0 6 1 1 6 2 0 7 0 0 7 1 0 7 2 0Have fun with this one!
UNIX> a.out 0 ngtr_digits(0) = 0. Total = 0 neq_digits(0) = 0. Total = 0 S=0 X=1 Answer=0 UNIX> a.out 1 ngtr_digits(0) = 3. Total = 3 ngtr_digits(1) = 0. Total = 3 ngtr_digits(2) = 0. Total = 3 neq_digits(0) = 0. Total = 3 neq_digits(1) = 0. Total = 3 neq_digits(2) = 0. Total = 3 S=101 X=9 Answer=3 UNIX> a.out 2 ngtr_digits(0) = 1. Total = 1 ngtr_digits(1) = 0. Total = 1 ngtr_digits(2) = 0. Total = 1 neq_digits(0) = 0. Total = 1 neq_digits(1) = 1. Total = 2 neq_digits(2) = 0. Total = 2 S=471 X=47 Answer=2 UNIX> a.out 3 ngtr_digits(0) = 4. Total = 4 ngtr_digits(1) = 1. Total = 5 ngtr_digits(2) = 0. Total = 5 ngtr_digits(3) = 0. Total = 5 neq_digits(0) = 0. Total = 5 neq_digits(1) = 0. Total = 5 neq_digits(2) = 0. Total = 5 neq_digits(3) = 0. Total = 5 S=2222 X=97 Answer=5 UNIX> a.out 4 ngtr_digits(0) = 99. Total = 99 ngtr_digits(1) = 42. Total = 141 ngtr_digits(2) = 16. Total = 157 ngtr_digits(3) = 5. Total = 162 ngtr_digits(4) = 1. Total = 163 ngtr_digits(5) = 0. Total = 163 ngtr_digits(6) = 0. Total = 163 ngtr_digits(7) = 0. Total = 163 neq_digits(0) = 21. Total = 184 neq_digits(1) = 15. Total = 199 neq_digits(2) = 10. Total = 209 neq_digits(3) = 4. Total = 213 neq_digits(4) = 3. Total = 216 neq_digits(5) = 0. Total = 216 neq_digits(6) = 0. Total = 216 neq_digits(7) = 0. Total = 216 S=95847362 X=436 Answer=216 UNIX> a.out 5 ngtr_digits(0) = 247. Total = 247 ngtr_digits(1) = 0. Total = 247 ngtr_digits(2) = 57. Total = 304 ngtr_digits(3) = 0. Total = 304 ngtr_digits(4) = 11. Total = 315 ngtr_digits(5) = 0. Total = 315 ngtr_digits(6) = 1. Total = 316 ngtr_digits(7) = 0. Total = 316 ngtr_digits(8) = 0. Total = 316 neq_digits(0) = 0. Total = 316 neq_digits(1) = 0. Total = 316 neq_digits(2) = 0. Total = 316 neq_digits(3) = 0. Total = 316 neq_digits(4) = 0. Total = 316 neq_digits(5) = 0. Total = 316 neq_digits(6) = 0. Total = 316 neq_digits(7) = 0. Total = 316 neq_digits(8) = 0. Total = 316 S=102030405 X=85 Answer=316 UNIX> a.out 6 ngtr_digits(0) = 1695222. Total = 1695222 ngtr_digits(1) = 0. Total = 1695222 ngtr_digits(2) = 354522. Total = 2049744 ngtr_digits(3) = 155382. Total = 2205126 ngtr_digits(4) = 65536. Total = 2270662 ngtr_digits(5) = 26333. Total = 2296995 ngtr_digits(6) = 9949. Total = 2306944 ngtr_digits(7) = 3473. Total = 2310417 ngtr_digits(8) = 1093. Total = 2311510 ngtr_digits(9) = 299. Total = 2311809 ngtr_digits(10) = 67. Total = 2311876 ngtr_digits(11) = 0. Total = 2311876 ngtr_digits(12) = 1. Total = 2311877 ngtr_digits(13) = 0. Total = 2311877 ngtr_digits(14) = 0. Total = 2311877 ngtr_digits(15) = 0. Total = 2311877 ngtr_digits(16) = 0. Total = 2311877 ngtr_digits(17) = 0. Total = 2311877 ngtr_digits(18) = 0. Total = 2311877 ngtr_digits(19) = 0. Total = 2311877 ngtr_digits(20) = 0. Total = 2311877 ngtr_digits(21) = 0. Total = 2311877 neq_digits(0) = 203490. Total = 2515367 neq_digits(1) = 0. Total = 2515367 neq_digits(2) = 5977. Total = 2521344 neq_digits(3) = 43758. Total = 2565102 neq_digits(4) = 0. Total = 2565102 neq_digits(5) = 12870. Total = 2577972 neq_digits(6) = 0. Total = 2577972 neq_digits(7) = 3003. Total = 2580975 neq_digits(8) = 1287. Total = 2582262 neq_digits(9) = 495. Total = 2582757 neq_digits(10) = 0. Total = 2582757 neq_digits(11) = 0. Total = 2582757 neq_digits(12) = 9. Total = 2582766 neq_digits(13) = 0. Total = 2582766 neq_digits(14) = 0. Total = 2582766 neq_digits(15) = 0. Total = 2582766 neq_digits(16) = 0. Total = 2582766 neq_digits(17) = 0. Total = 2582766 neq_digits(18) = 0. Total = 2582766 neq_digits(19) = 0. Total = 2582766 neq_digits(20) = 0. Total = 2582766 neq_digits(21) = 0. Total = 2582766 S=8034151889109199226907 X=368249157 Answer=2582766 UNIX> a.out 7 ngtr_digits(0) = 2143911424. Total = 2143911424 ngtr_digits(1) = 1070937812. Total = 3214849236 ngtr_digits(2) = 0. Total = 3214849236 ngtr_digits(3) = 266752238. Total = 3481601474 ngtr_digits(4) = 132932104. Total = 3614533578 ngtr_digits(5) = 0. Total = 3614533578 ngtr_digits(6) = 32828226. Total = 3647361804 ngtr_digits(7) = 16241061. Total = 3663602865 ngtr_digits(8) = 7997952. Total = 3671600817 ngtr_digits(9) = 3913704. Total = 3675514521 ngtr_digits(10) = 1898712. Total = 3677413233 ngtr_digits(11) = 910596. Total = 3678323829 ngtr_digits(12) = 430104. Total = 3678753933 ngtr_digits(13) = 199140. Total = 3678953073 ngtr_digits(14) = 89846. Total = 3679042919 ngtr_digits(15) = 39203. Total = 3679082122 ngtr_digits(16) = 0. Total = 3679082122 ngtr_digits(17) = 6476. Total = 3679088598 ngtr_digits(18) = 2380. Total = 3679090978 ngtr_digits(19) = 794. Total = 3679091772 ngtr_digits(20) = 0. Total = 3679091772 ngtr_digits(21) = 0. Total = 3679091772 ngtr_digits(22) = 10. Total = 3679091782 ngtr_digits(23) = 1. Total = 3679091783 ngtr_digits(24) = 0. Total = 3679091783 ngtr_digits(25) = 0. Total = 3679091783 ngtr_digits(26) = 0. Total = 3679091783 ngtr_digits(27) = 0. Total = 3679091783 ngtr_digits(28) = 0. Total = 3679091783 ngtr_digits(29) = 0. Total = 3679091783 ngtr_digits(30) = 0. Total = 3679091783 ngtr_digits(31) = 0. Total = 3679091783 neq_digits(0) = 2629575. Total = 3681721358 neq_digits(1) = 2035800. Total = 3683757158 neq_digits(2) = 0. Total = 3683757158 neq_digits(3) = 0. Total = 3683757158 neq_digits(4) = 888030. Total = 3684645188 neq_digits(5) = 0. Total = 3684645188 neq_digits(6) = 480700. Total = 3685125888 neq_digits(7) = 0. Total = 3685125888 neq_digits(8) = 245157. Total = 3685371045 neq_digits(9) = 170544. Total = 3685541589 neq_digits(10) = 116280. Total = 3685657869 neq_digits(11) = 77520. Total = 3685735389 neq_digits(12) = 0. Total = 3685735389 neq_digits(13) = 31824. Total = 3685767213 neq_digits(14) = 19448. Total = 3685786661 neq_digits(15) = 0. Total = 3685786661 neq_digits(16) = 0. Total = 3685786661 neq_digits(17) = 1835. Total = 3685788496 neq_digits(18) = 1716. Total = 3685790212 neq_digits(19) = 0. Total = 3685790212 neq_digits(20) = 0. Total = 3685790212 neq_digits(21) = 0. Total = 3685790212 neq_digits(22) = 36. Total = 3685790248 neq_digits(23) = 8. Total = 3685790256 neq_digits(24) = 1. Total = 3685790257 neq_digits(25) = 0. Total = 3685790257 neq_digits(26) = 0. Total = 3685790257 neq_digits(27) = 0. Total = 3685790257 neq_digits(28) = 0. Total = 3685790257 neq_digits(29) = 0. Total = 3685790257 neq_digits(30) = 0. Total = 3685790257 neq_digits(31) = 0. Total = 3685790257 S=54019091675924410392006963001976 X=33857108 Answer=3685790257 UNIX> a.out 8 ngtr_digits(0) = 140737098539113. Total = 140737098539113 ngtr_digits(1) = 70368418803149. Total = 211105517342262 ngtr_digits(2) = 35184101624977. Total = 246289618967239 ngtr_digits(3) = 17591962196175. Total = 263881581163414 ngtr_digits(4) = 8795908593831. Total = 272677489757245 ngtr_digits(5) = 4397895281823. Total = 277075385039068 ngtr_digits(6) = 2198899866789. Total = 279274284905857 ngtr_digits(7) = 1099411481052. Total = 280373696386909 ngtr_digits(8) = 549674978652. Total = 280923371365561 ngtr_digits(9) = 274813037580. Total = 281198184403141 ngtr_digits(10) = 137387214780. Total = 281335571617921 ngtr_digits(11) = 68678477220. Total = 281404250095141 ngtr_digits(12) = 34327470700. Total = 281438577565841 ngtr_digits(13) = 0. Total = 281438577565841 ngtr_digits(14) = 8570386546. Total = 281447147952387 ngtr_digits(15) = 4279934123. Total = 281451427886510 ngtr_digits(16) = 2136022699. Total = 281453563909209 ngtr_digits(17) = 0. Total = 281453563909209 ngtr_digits(18) = 530396371. Total = 281454094305580 ngtr_digits(19) = 263644133. Total = 281454357949713 ngtr_digits(20) = 130712029. Total = 281454488661742 ngtr_digits(21) = 0. Total = 281454488661742 ngtr_digits(22) = 0. Total = 281454488661742 ngtr_digits(23) = 0. Total = 281454488661742 ngtr_digits(24) = 0. Total = 281454488661742 ngtr_digits(25) = 0. Total = 281454488661742 ngtr_digits(26) = 0. Total = 281454488661742 ngtr_digits(27) = 0. Total = 281454488661742 ngtr_digits(28) = 0. Total = 281454488661742 ngtr_digits(29) = 0. Total = 281454488661742 ngtr_digits(30) = 0. Total = 281454488661742 ngtr_digits(31) = 0. Total = 281454488661742 ngtr_digits(32) = 0. Total = 281454488661742 ngtr_digits(33) = 0. Total = 281454488661742 ngtr_digits(34) = 0. Total = 281454488661742 ngtr_digits(35) = 0. Total = 281454488661742 ngtr_digits(36) = 0. Total = 281454488661742 ngtr_digits(37) = 0. Total = 281454488661742 ngtr_digits(38) = 0. Total = 281454488661742 ngtr_digits(39) = 0. Total = 281454488661742 ngtr_digits(40) = 0. Total = 281454488661742 ngtr_digits(41) = 0. Total = 281454488661742 ngtr_digits(42) = 0. Total = 281454488661742 ngtr_digits(43) = 0. Total = 281454488661742 ngtr_digits(44) = 0. Total = 281454488661742 ngtr_digits(45) = 0. Total = 281454488661742 ngtr_digits(46) = 0. Total = 281454488661742 ngtr_digits(47) = 0. Total = 281454488661742 neq_digits(0) = 314457495. Total = 281454803119237 neq_digits(1) = 0. Total = 281454803119237 neq_digits(2) = 215553195. Total = 281455018672432 neq_digits(3) = 177232627. Total = 281455195905059 neq_digits(4) = 145008513. Total = 281455340913572 neq_digits(5) = 118030185. Total = 281455458943757 neq_digits(6) = 0. Total = 281455458943757 neq_digits(7) = 1705057. Total = 281455460648814 neq_digits(8) = 1705057. Total = 281455462353871 neq_digits(9) = 0. Total = 281455462353871 neq_digits(10) = 0. Total = 281455462353871 neq_digits(11) = 0. Total = 281455462353871 neq_digits(12) = 0. Total = 281455462353871 neq_digits(13) = 0. Total = 281455462353871 neq_digits(14) = 1705057. Total = 281455464058928 neq_digits(15) = 10518300. Total = 281455474577228 neq_digits(16) = 7888725. Total = 281455482465953 neq_digits(17) = 0. Total = 281455482465953 neq_digits(18) = 0. Total = 281455482465953 neq_digits(19) = 3108105. Total = 281455485574058 neq_digits(20) = 2220075. Total = 281455487794133 neq_digits(21) = 0. Total = 281455487794133 neq_digits(22) = 0. Total = 281455487794133 neq_digits(23) = 0. Total = 281455487794133 neq_digits(24) = 0. Total = 281455487794133 neq_digits(25) = 0. Total = 281455487794133 neq_digits(26) = 0. Total = 281455487794133 neq_digits(27) = 0. Total = 281455487794133 neq_digits(28) = 0. Total = 281455487794133 neq_digits(29) = 0. Total = 281455487794133 neq_digits(30) = 0. Total = 281455487794133 neq_digits(31) = 0. Total = 281455487794133 neq_digits(32) = 0. Total = 281455487794133 neq_digits(33) = 0. Total = 281455487794133 neq_digits(34) = 0. Total = 281455487794133 neq_digits(35) = 0. Total = 281455487794133 neq_digits(36) = 0. Total = 281455487794133 neq_digits(37) = 0. Total = 281455487794133 neq_digits(38) = 0. Total = 281455487794133 neq_digits(39) = 0. Total = 281455487794133 neq_digits(40) = 0. Total = 281455487794133 neq_digits(41) = 0. Total = 281455487794133 neq_digits(42) = 0. Total = 281455487794133 neq_digits(43) = 0. Total = 281455487794133 neq_digits(44) = 0. Total = 281455487794133 neq_digits(45) = 0. Total = 281455487794133 neq_digits(46) = 0. Total = 281455487794133 neq_digits(47) = 0. Total = 281455487794133 S=949778566115406970397000000000000000000079641169 X=694874013 Answer=281455487794133 UNIX> a.out 9 ngtr_digits(0) = 140737098539113. Total = 140737098539113 ngtr_digits(1) = 70368418803149. Total = 211105517342262 ngtr_digits(2) = 0. Total = 211105517342262 ngtr_digits(3) = 17591962196175. Total = 228697479538437 ngtr_digits(4) = 8795908593831. Total = 237493388132268 ngtr_digits(5) = 0. Total = 237493388132268 ngtr_digits(6) = 2198899866789. Total = 239692287999057 ngtr_digits(7) = 1099411481052. Total = 240791699480109 ngtr_digits(8) = 549674978652. Total = 241341374458761 ngtr_digits(9) = 274813037580. Total = 241616187496341 ngtr_digits(10) = 137387214780. Total = 241753574711121 ngtr_digits(11) = 68678477220. Total = 241822253188341 ngtr_digits(12) = 34327470700. Total = 241856580659041 ngtr_digits(13) = 17154657248. Total = 241873735316289 ngtr_digits(14) = 8570386546. Total = 241882305702835 ngtr_digits(15) = 4279934123. Total = 241886585636958 ngtr_digits(16) = 2136022699. Total = 241888721659657 ngtr_digits(17) = 1065084887. Total = 241889786744544 ngtr_digits(18) = 530396371. Total = 241890317140915 ngtr_digits(19) = 263644133. Total = 241890580785048 ngtr_digits(20) = 130712029. Total = 241890711497077 ngtr_digits(21) = 64574877. Total = 241890776071954 ngtr_digits(22) = 31746651. Total = 241890807818605 ngtr_digits(23) = 15505590. Total = 241890823324195 ngtr_digits(24) = 7507638. Total = 241890830831833 ngtr_digits(25) = 3593934. Total = 241890834425767 ngtr_digits(26) = 1695222. Total = 241890836120989 ngtr_digits(27) = 784626. Total = 241890836905615 ngtr_digits(28) = 354522. Total = 241890837260137 ngtr_digits(29) = 155382. Total = 241890837415519 ngtr_digits(30) = 65536. Total = 241890837481055 ngtr_digits(31) = 26333. Total = 241890837507388 ngtr_digits(32) = 9949. Total = 241890837517337 ngtr_digits(33) = 3473. Total = 241890837520810 ngtr_digits(34) = 1093. Total = 241890837521903 ngtr_digits(35) = 299. Total = 241890837522202 ngtr_digits(36) = 67. Total = 241890837522269 ngtr_digits(37) = 11. Total = 241890837522280 ngtr_digits(38) = 1. Total = 241890837522281 ngtr_digits(39) = 0. Total = 241890837522281 ngtr_digits(40) = 0. Total = 241890837522281 ngtr_digits(41) = 0. Total = 241890837522281 ngtr_digits(42) = 0. Total = 241890837522281 ngtr_digits(43) = 0. Total = 241890837522281 ngtr_digits(44) = 0. Total = 241890837522281 ngtr_digits(45) = 0. Total = 241890837522281 ngtr_digits(46) = 0. Total = 241890837522281 ngtr_digits(47) = 0. Total = 241890837522281 neq_digits(0) = 314457495. Total = 241891151979776 neq_digits(1) = 260932815. Total = 241891412912591 neq_digits(2) = 0. Total = 241891412912591 neq_digits(3) = 0. Total = 241891412912591 neq_digits(4) = 0. Total = 241891412912591 neq_digits(5) = 0. Total = 241891412912591 neq_digits(6) = 95548245. Total = 241891508460836 neq_digits(7) = 0. Total = 241891508460836 neq_digits(8) = 0. Total = 241891508460836 neq_digits(9) = 10697754. Total = 241891519158590 neq_digits(10) = 0. Total = 241891519158590 neq_digits(11) = 0. Total = 241891519158590 neq_digits(12) = 0. Total = 241891519158590 neq_digits(13) = 18156204. Total = 241891537314794 neq_digits(14) = 0. Total = 241891537314794 neq_digits(15) = 0. Total = 241891537314794 neq_digits(16) = 3995409. Total = 241891541310203 neq_digits(17) = 0. Total = 241891541310203 neq_digits(18) = 4292145. Total = 241891545602348 neq_digits(19) = 3108105. Total = 241891548710453 neq_digits(20) = 2220075. Total = 241891550930528 neq_digits(21) = 0. Total = 241891550930528 neq_digits(22) = 0. Total = 241891550930528 neq_digits(23) = 0. Total = 241891550930528 neq_digits(24) = 490314. Total = 241891551420842 neq_digits(25) = 0. Total = 241891551420842 neq_digits(26) = 77970. Total = 241891551498812 neq_digits(27) = 125970. Total = 241891551624782 neq_digits(28) = 0. Total = 241891551624782 neq_digits(29) = 0. Total = 241891551624782 neq_digits(30) = 0. Total = 241891551624782 neq_digits(31) = 0. Total = 241891551624782 neq_digits(32) = 0. Total = 241891551624782 neq_digits(33) = 0. Total = 241891551624782 neq_digits(34) = 0. Total = 241891551624782 neq_digits(35) = 0. Total = 241891551624782 neq_digits(36) = 165. Total = 241891551624947 neq_digits(37) = 45. Total = 241891551624992 neq_digits(38) = 0. Total = 241891551624992 neq_digits(39) = 0. Total = 241891551624992 neq_digits(40) = 0. Total = 241891551624992 neq_digits(41) = 0. Total = 241891551624992 neq_digits(42) = 0. Total = 241891551624992 neq_digits(43) = 0. Total = 241891551624992 neq_digits(44) = 0. Total = 241891551624992 neq_digits(45) = 0. Total = 241891551624992 neq_digits(46) = 0. Total = 241891551624992 neq_digits(47) = 0. Total = 241891551624992 S=990450814731595674899314817951534213891202482671 X=777444111 Answer=241891551624992 UNIX> a.out 10 ngtr_digits(0) = 140737412996608. Total = 140737412996608 ngtr_digits(1) = 0. Total = 140737412996608 ngtr_digits(2) = 35184317178172. Total = 175921730174780 ngtr_digits(3) = 17592139428802. Total = 193513869603582 ngtr_digits(4) = 0. Total = 193513869603582 ngtr_digits(5) = 4398013312008. Total = 197911882915590 ngtr_digits(6) = 2198995415034. Total = 200110878330624 ngtr_digits(7) = 0. Total = 200110878330624 ngtr_digits(8) = 0. Total = 200110878330624 ngtr_digits(9) = 0. Total = 200110878330624 ngtr_digits(10) = 0. Total = 200110878330624 ngtr_digits(11) = 0. Total = 200110878330624 ngtr_digits(12) = 0. Total = 200110878330624 ngtr_digits(13) = 0. Total = 200110878330624 ngtr_digits(14) = 0. Total = 200110878330624 ngtr_digits(15) = 4290452423. Total = 200115168783047 ngtr_digits(16) = 2143911424. Total = 200117312694471 ngtr_digits(17) = 1070937812. Total = 200118383632283 ngtr_digits(18) = 534688516. Total = 200118918320799 ngtr_digits(19) = 266752238. Total = 200119185073037 ngtr_digits(20) = 132932104. Total = 200119318005141 ngtr_digits(21) = 66137152. Total = 200119384142293 ngtr_digits(22) = 32828226. Total = 200119416970519 ngtr_digits(23) = 16241061. Total = 200119433211580 ngtr_digits(24) = 7997952. Total = 200119441209532 ngtr_digits(25) = 3913704. Total = 200119445123236 ngtr_digits(26) = 0. Total = 200119445123236 ngtr_digits(27) = 910596. Total = 200119446033832 ngtr_digits(28) = 430104. Total = 200119446463936 ngtr_digits(29) = 199140. Total = 200119446663076 ngtr_digits(30) = 89846. Total = 200119446752922 ngtr_digits(31) = 39203. Total = 200119446792125 ngtr_digits(32) = 16384. Total = 200119446808509 ngtr_digits(33) = 6476. Total = 200119446814985 ngtr_digits(34) = 2380. Total = 200119446817365 ngtr_digits(35) = 794. Total = 200119446818159 ngtr_digits(36) = 232. Total = 200119446818391 ngtr_digits(37) = 56. Total = 200119446818447 ngtr_digits(38) = 10. Total = 200119446818457 ngtr_digits(39) = 1. Total = 200119446818458 ngtr_digits(40) = 0. Total = 200119446818458 ngtr_digits(41) = 0. Total = 200119446818458 ngtr_digits(42) = 0. Total = 200119446818458 ngtr_digits(43) = 0. Total = 200119446818458 ngtr_digits(44) = 0. Total = 200119446818458 ngtr_digits(45) = 0. Total = 200119446818458 ngtr_digits(46) = 0. Total = 200119446818458 ngtr_digits(47) = 0. Total = 200119446818458 neq_digits(0) = 62891499. Total = 200119509709957 neq_digits(1) = 0. Total = 200119509709957 neq_digits(2) = 45379620. Total = 200119555089577 neq_digits(3) = 38320568. Total = 200119593410145 neq_digits(4) = 0. Total = 200119593410145 neq_digits(5) = 26978328. Total = 200119620388473 neq_digits(6) = 22481940. Total = 200119642870413 neq_digits(7) = 0. Total = 200119642870413 neq_digits(8) = 0. Total = 200119642870413 neq_digits(9) = 0. Total = 200119642870413 neq_digits(10) = 0. Total = 200119642870413 neq_digits(11) = 0. Total = 200119642870413 neq_digits(12) = 0. Total = 200119642870413 neq_digits(13) = 0. Total = 200119642870413 neq_digits(14) = 0. Total = 200119642870413 neq_digits(15) = 3365856. Total = 200119646236269 neq_digits(16) = 1988863. Total = 200119648225132 neq_digits(17) = 2035800. Total = 200119650260932 neq_digits(18) = 1560780. Total = 200119651821712 neq_digits(19) = 1184040. Total = 200119653005752 neq_digits(20) = 543328. Total = 200119653549080 neq_digits(21) = 657800. Total = 200119654206880 neq_digits(22) = 480700. Total = 200119654687580 neq_digits(23) = 135998. Total = 200119654823578 neq_digits(24) = 135998. Total = 200119654959576 neq_digits(25) = 170544. Total = 200119655130120 neq_digits(26) = 0. Total = 200119655130120 neq_digits(27) = 77520. Total = 200119655207640 neq_digits(28) = 50388. Total = 200119655258028 neq_digits(29) = 31824. Total = 200119655289852 neq_digits(30) = 19448. Total = 200119655309300 neq_digits(31) = 11440. Total = 200119655320740 neq_digits(32) = 6435. Total = 200119655327175 neq_digits(33) = 3432. Total = 200119655330607 neq_digits(34) = 1716. Total = 200119655332323 neq_digits(35) = 792. Total = 200119655333115 neq_digits(36) = 330. Total = 200119655333445 neq_digits(37) = 120. Total = 200119655333565 neq_digits(38) = 1. Total = 200119655333566 neq_digits(39) = 8. Total = 200119655333574 neq_digits(40) = 1. Total = 200119655333575 neq_digits(41) = 0. Total = 200119655333575 neq_digits(42) = 0. Total = 200119655333575 neq_digits(43) = 0. Total = 200119655333575 neq_digits(44) = 0. Total = 200119655333575 neq_digits(45) = 0. Total = 200119655333575 neq_digits(46) = 0. Total = 200119655333575 neq_digits(47) = 0. Total = 200119655333575 S=906708300000000816661861190246822256891226113143 X=13879163 Answer=200119655333575 UNIX> a.out 11 ngtr_digits(0) = 140737488159619. Total = 140737488159619 ngtr_digits(1) = 70368743998217. Total = 211106232157836 ngtr_digits(2) = 35184371924611. Total = 246290604082447 ngtr_digits(3) = 17592185894430. Total = 263882789976877 ngtr_digits(4) = 8796092885510. Total = 272678882862387 ngtr_digits(5) = 4398046386790. Total = 277076929249177 ngtr_digits(6) = 2199023142760. Total = 279275952391937 ngtr_digits(7) = 1099511525685. Total = 280375463917622 ngtr_digits(8) = 549755721717. Total = 280925219639339 ngtr_digits(9) = 274877823951. Total = 281200097463290 ngtr_digits(10) = 137438878953. Total = 281337536342243 ngtr_digits(11) = 68719410024. Total = 281406255752267 ngtr_digits(12) = 34359678832. Total = 281440615431099 ngtr_digits(13) = 17179816228. Total = 281457795247327 ngtr_digits(14) = 8589887654. Total = 281466385134981 ngtr_digits(15) = 4294925847. Total = 281470680060828 ngtr_digits(16) = 2147447191. Total = 281472827508019 ngtr_digits(17) = 1073709893. Total = 281473901217912 ngtr_digits(18) = 536843071. Total = 281474438060983 ngtr_digits(19) = 0. Total = 281474438060983 ngtr_digits(20) = 134196874. Total = 281474572257857 ngtr_digits(21) = 67090962. Total = 281474639348819 ngtr_digits(22) = 33539156. Total = 281474672887975 ngtr_digits(23) = 16764265. Total = 281474689652240 ngtr_digits(24) = 8377705. Total = 281474698029945 ngtr_digits(25) = 4185195. Total = 281474702215140 ngtr_digits(26) = 2089605. Total = 281474704304745 ngtr_digits(27) = 1042380. Total = 281474705347125 ngtr_digits(28) = 519252. Total = 281474705866377 ngtr_digits(29) = 258096. Total = 281474706124473 ngtr_digits(30) = 127858. Total = 281474706252331 ngtr_digits(31) = 63019. Total = 281474706315350 ngtr_digits(32) = 30827. Total = 281474706346177 ngtr_digits(33) = 14913. Total = 281474706361090 ngtr_digits(34) = 7099. Total = 281474706368189 ngtr_digits(35) = 3302. Total = 281474706371491 ngtr_digits(36) = 1486. Total = 281474706372977 ngtr_digits(37) = 638. Total = 281474706373615 ngtr_digits(38) = 256. Total = 281474706373871 ngtr_digits(39) = 0. Total = 281474706373871 ngtr_digits(40) = 0. Total = 281474706373871 ngtr_digits(41) = 7. Total = 281474706373878 ngtr_digits(42) = 1. Total = 281474706373879 ngtr_digits(43) = 0. Total = 281474706373879 ngtr_digits(44) = 0. Total = 281474706373879 ngtr_digits(45) = 0. Total = 281474706373879 ngtr_digits(46) = 0. Total = 281474706373879 ngtr_digits(47) = 0. Total = 281474706373879 neq_digits(0) = 178365. Total = 281474706552244 neq_digits(1) = 163185. Total = 281474706715429 neq_digits(2) = 148995. Total = 281474706864424 neq_digits(3) = 135751. Total = 281474707000175 neq_digits(4) = 123410. Total = 281474707123585 neq_digits(5) = 0. Total = 281474707123585 neq_digits(6) = 0. Total = 281474707123585 neq_digits(7) = 91390. Total = 281474707214975 neq_digits(8) = 82251. Total = 281474707297226 neq_digits(9) = 32739. Total = 281474707329965 neq_digits(10) = 66045. Total = 281474707396010 neq_digits(11) = 58905. Total = 281474707454915 neq_digits(12) = 25599. Total = 281474707480514 neq_digits(13) = 46376. Total = 281474707526890 neq_digits(14) = 40920. Total = 281474707567810 neq_digits(15) = 35960. Total = 281474707603770 neq_digits(16) = 31465. Total = 281474707635235 neq_digits(17) = 27405. Total = 281474707662640 neq_digits(18) = 23751. Total = 281474707686391 neq_digits(19) = 0. Total = 281474707686391 neq_digits(20) = 17550. Total = 281474707703941 neq_digits(21) = 3581. Total = 281474707707522 neq_digits(22) = 12650. Total = 281474707720172 neq_digits(23) = 10626. Total = 281474707730798 neq_digits(24) = 8855. Total = 281474707739653 neq_digits(25) = 7315. Total = 281474707746968 neq_digits(26) = 5985. Total = 281474707752953 neq_digits(27) = 0. Total = 281474707752953 neq_digits(28) = 3876. Total = 281474707756829 neq_digits(29) = 3060. Total = 281474707759889 neq_digits(30) = 2380. Total = 281474707762269 neq_digits(31) = 1820. Total = 281474707764089 neq_digits(32) = 1365. Total = 281474707765454 neq_digits(33) = 0. Total = 281474707765454 neq_digits(34) = 715. Total = 281474707766169 neq_digits(35) = 10. Total = 281474707766179 neq_digits(36) = 330. Total = 281474707766509 neq_digits(37) = 210. Total = 281474707766719 neq_digits(38) = 126. Total = 281474707766845 neq_digits(39) = 0. Total = 281474707766845 neq_digits(40) = 0. Total = 281474707766845 neq_digits(41) = 15. Total = 281474707766860 neq_digits(42) = 5. Total = 281474707766865 neq_digits(43) = 1. Total = 281474707766866 neq_digits(44) = 0. Total = 281474707766866 neq_digits(45) = 0. Total = 281474707766866 neq_digits(46) = 0. Total = 281474707766866 neq_digits(47) = 0. Total = 281474707766866 S=547371145238239979608276364147467162445006834154 X=26862 Answer=281474707766866 UNIX> a.out 12 ngtr_digits(0) = 140737412996608. Total = 140737412996608 ngtr_digits(1) = 70368679735964. Total = 211106092732572 ngtr_digits(2) = 0. Total = 211106092732572 ngtr_digits(3) = 0. Total = 211106092732572 ngtr_digits(4) = 0. Total = 211106092732572 ngtr_digits(5) = 0. Total = 211106092732572 ngtr_digits(6) = 0. Total = 211106092732572 ngtr_digits(7) = 1099488385737. Total = 212205581118309 ngtr_digits(8) = 549736502400. Total = 212755317620709 ngtr_digits(9) = 274861941072. Total = 213030179561781 ngtr_digits(10) = 0. Total = 213030179561781 ngtr_digits(11) = 68708737560. Total = 213098888299341 ngtr_digits(12) = 34351006520. Total = 213133239305861 ngtr_digits(13) = 17172813452. Total = 213150412119313 ngtr_digits(14) = 8584270702. Total = 213158996390015 ngtr_digits(15) = 0. Total = 213158996390015 ngtr_digits(16) = 2143911424. Total = 213161140301439 ngtr_digits(17) = 1070937812. Total = 213162211239251 ngtr_digits(18) = 534688516. Total = 213162745927767 ngtr_digits(19) = 266752238. Total = 213163012680005 ngtr_digits(20) = 0. Total = 213163012680005 ngtr_digits(21) = 0. Total = 213163012680005 ngtr_digits(22) = 0. Total = 213163012680005 ngtr_digits(23) = 16241061. Total = 213163028921066 ngtr_digits(24) = 7997952. Total = 213163036919018 ngtr_digits(25) = 3913704. Total = 213163040832722 ngtr_digits(26) = 1898712. Total = 213163042731434 ngtr_digits(27) = 910596. Total = 213163043642030 ngtr_digits(28) = 430104. Total = 213163044072134 ngtr_digits(29) = 199140. Total = 213163044271274 ngtr_digits(30) = 89846. Total = 213163044361120 ngtr_digits(31) = 39203. Total = 213163044400323 ngtr_digits(32) = 16384. Total = 213163044416707 ngtr_digits(33) = 0. Total = 213163044416707 ngtr_digits(34) = 0. Total = 213163044416707 ngtr_digits(35) = 0. Total = 213163044416707 ngtr_digits(36) = 0. Total = 213163044416707 ngtr_digits(37) = 0. Total = 213163044416707 ngtr_digits(38) = 0. Total = 213163044416707 ngtr_digits(39) = 1. Total = 213163044416708 ngtr_digits(40) = 0. Total = 213163044416708 ngtr_digits(41) = 0. Total = 213163044416708 ngtr_digits(42) = 0. Total = 213163044416708 ngtr_digits(43) = 0. Total = 213163044416708 ngtr_digits(44) = 0. Total = 213163044416708 ngtr_digits(45) = 0. Total = 213163044416708 ngtr_digits(46) = 0. Total = 213163044416708 ngtr_digits(47) = 0. Total = 213163044416708 neq_digits(0) = 0. Total = 213163044416708 neq_digits(1) = 0. Total = 213163044416708 neq_digits(2) = 0. Total = 213163044416708 neq_digits(3) = 0. Total = 213163044416708 neq_digits(4) = 0. Total = 213163044416708 neq_digits(5) = 0. Total = 213163044416708 neq_digits(6) = 0. Total = 213163044416708 neq_digits(7) = 18643560. Total = 213163063060268 neq_digits(8) = 0. Total = 213163063060268 neq_digits(9) = 0. Total = 213163063060268 neq_digits(10) = 0. Total = 213163063060268 neq_digits(11) = 0. Total = 213163063060268 neq_digits(12) = 0. Total = 213163063060268 neq_digits(13) = 0. Total = 213163063060268 neq_digits(14) = 0. Total = 213163063060268 neq_digits(15) = 0. Total = 213163063060268 neq_digits(16) = 0. Total = 213163063060268 neq_digits(17) = 0. Total = 213163063060268 neq_digits(18) = 457048. Total = 213163063517316 neq_digits(19) = 0. Total = 213163063517316 neq_digits(20) = 0. Total = 213163063517316 neq_digits(21) = 0. Total = 213163063517316 neq_digits(22) = 0. Total = 213163063517316 neq_digits(23) = 346104. Total = 213163063863420 neq_digits(24) = 0. Total = 213163063863420 neq_digits(25) = 0. Total = 213163063863420 neq_digits(26) = 0. Total = 213163063863420 neq_digits(27) = 0. Total = 213163063863420 neq_digits(28) = 38984. Total = 213163063902404 neq_digits(29) = 31824. Total = 213163063934228 neq_digits(30) = 19448. Total = 213163063953676 neq_digits(31) = 0. Total = 213163063953676 neq_digits(32) = 0. Total = 213163063953676 neq_digits(33) = 0. Total = 213163063953676 neq_digits(34) = 0. Total = 213163063953676 neq_digits(35) = 0. Total = 213163063953676 neq_digits(36) = 0. Total = 213163063953676 neq_digits(37) = 0. Total = 213163063953676 neq_digits(38) = 0. Total = 213163063953676 neq_digits(39) = 8. Total = 213163063953684 neq_digits(40) = 0. Total = 213163063953684 neq_digits(41) = 0. Total = 213163063953684 neq_digits(42) = 0. Total = 213163063953684 neq_digits(43) = 0. Total = 213163063953684 neq_digits(44) = 0. Total = 213163063953684 neq_digits(45) = 0. Total = 213163063953684 neq_digits(46) = 0. Total = 213163063953684 neq_digits(47) = 0. Total = 213163063953684 S=550000096205335065730009666579861000000769420768 X=75676722 Answer=213163063953684 UNIX> a.out 13 ngtr_digits(0) = 140737098539113. Total = 140737098539113 ngtr_digits(1) = 70368418803149. Total = 211105517342262 ngtr_digits(2) = 35184101624977. Total = 246289618967239 ngtr_digits(3) = 17591962196175. Total = 263881581163414 ngtr_digits(4) = 8795908593831. Total = 272677489757245 ngtr_digits(5) = 4397895281823. Total = 277075385039068 ngtr_digits(6) = 2198899866789. Total = 279274284905857 ngtr_digits(7) = 1099411481052. Total = 280373696386909 ngtr_digits(8) = 549674978652. Total = 280923371365561 ngtr_digits(9) = 274813037580. Total = 281198184403141 ngtr_digits(10) = 137387214780. Total = 281335571617921 ngtr_digits(11) = 68678477220. Total = 281404250095141 ngtr_digits(12) = 34327470700. Total = 281438577565841 ngtr_digits(13) = 17154657248. Total = 281455732223089 ngtr_digits(14) = 8570386546. Total = 281464302609635 ngtr_digits(15) = 0. Total = 281464302609635 ngtr_digits(16) = 2136022699. Total = 281466438632334 ngtr_digits(17) = 1065084887. Total = 281467503717221 ngtr_digits(18) = 530396371. Total = 281468034113592 ngtr_digits(19) = 263644133. Total = 281468297757725 ngtr_digits(20) = 130712029. Total = 281468428469754 ngtr_digits(21) = 64574877. Total = 281468493044631 ngtr_digits(22) = 31746651. Total = 281468524791282 ngtr_digits(23) = 15505590. Total = 281468540296872 ngtr_digits(24) = 0. Total = 281468540296872 ngtr_digits(25) = 3593934. Total = 281468543890806 ngtr_digits(26) = 1695222. Total = 281468545586028 ngtr_digits(27) = 784626. Total = 281468546370654 ngtr_digits(28) = 354522. Total = 281468546725176 ngtr_digits(29) = 0. Total = 281468546725176 ngtr_digits(30) = 65536. Total = 281468546790712 ngtr_digits(31) = 0. Total = 281468546790712 ngtr_digits(32) = 9949. Total = 281468546800661 ngtr_digits(33) = 3473. Total = 281468546804134 ngtr_digits(34) = 1093. Total = 281468546805227 ngtr_digits(35) = 299. Total = 281468546805526 ngtr_digits(36) = 0. Total = 281468546805526 ngtr_digits(37) = 11. Total = 281468546805537 ngtr_digits(38) = 1. Total = 281468546805538 ngtr_digits(39) = 0. Total = 281468546805538 ngtr_digits(40) = 0. Total = 281468546805538 ngtr_digits(41) = 0. Total = 281468546805538 ngtr_digits(42) = 0. Total = 281468546805538 ngtr_digits(43) = 0. Total = 281468546805538 ngtr_digits(44) = 0. Total = 281468546805538 ngtr_digits(45) = 0. Total = 281468546805538 ngtr_digits(46) = 0. Total = 281468546805538 ngtr_digits(47) = 0. Total = 281468546805538 neq_digits(0) = 314457495. Total = 281468861263033 neq_digits(1) = 208611211. Total = 281469069874244 neq_digits(2) = 215553195. Total = 281469285427439 neq_digits(3) = 177232627. Total = 281469462660066 neq_digits(4) = 0. Total = 281469462660066 neq_digits(5) = 118030185. Total = 281469580690251 neq_digits(6) = 66368826. Total = 281469647059077 neq_digits(7) = 0. Total = 281469647059077 neq_digits(8) = 0. Total = 281469647059077 neq_digits(9) = 35105010. Total = 281469682164087 neq_digits(10) = 0. Total = 281469682164087 neq_digits(11) = 0. Total = 281469682164087 neq_digits(12) = 23535820. Total = 281469705699907 neq_digits(13) = 18156204. Total = 281469723856111 neq_digits(14) = 0. Total = 281469723856111 neq_digits(15) = 0. Total = 281469723856111 neq_digits(16) = 0. Total = 281469723856111 neq_digits(17) = 5852925. Total = 281469729709036 neq_digits(18) = 0. Total = 281469729709036 neq_digits(19) = 0. Total = 281469729709036 neq_digits(20) = 0. Total = 281469729709036 neq_digits(21) = 776092. Total = 281469730485128 neq_digits(22) = 1081575. Total = 281469731566703 neq_digits(23) = 0. Total = 281469731566703 neq_digits(24) = 0. Total = 281469731566703 neq_digits(25) = 0. Total = 281469731566703 neq_digits(26) = 203490. Total = 281469731770193 neq_digits(27) = 125970. Total = 281469731896163 neq_digits(28) = 0. Total = 281469731896163 neq_digits(29) = 0. Total = 281469731896163 neq_digits(30) = 0. Total = 281469731896163 neq_digits(31) = 0. Total = 281469731896163 neq_digits(32) = 0. Total = 281469731896163 neq_digits(33) = 3003. Total = 281469731899166 neq_digits(34) = 0. Total = 281469731899166 neq_digits(35) = 495. Total = 281469731899661 neq_digits(36) = 0. Total = 281469731899661 neq_digits(37) = 45. Total = 281469731899706 neq_digits(38) = 9. Total = 281469731899715 neq_digits(39) = 1. Total = 281469731899716 neq_digits(40) = 0. Total = 281469731899716 neq_digits(41) = 0. Total = 281469731899716 neq_digits(42) = 0. Total = 281469731899716 neq_digits(43) = 0. Total = 281469731899716 neq_digits(44) = 0. Total = 281469731899716 neq_digits(45) = 0. Total = 281469731899716 neq_digits(46) = 0. Total = 281469731899716 neq_digits(47) = 0. Total = 281469731899716 S=957837542544882028114572037810101728066730780324 X=536624519 Answer=281469731899716 UNIX>