趣题：从1到4000中各位数字之和能被4整除的有多少个？.doc

看见的一道小学奥数题：从 1 到 4000 中，各位数字之和能被 4 整除的有多少个？注意，问题可能没有你想的那么简单，满足要求的数分布得并没有那么规则。 1 、 2 、 3 、 4 里有一个满足要求的数， 5 、 6 、 7 、 8 里也有一个满足要求的数，但是 9 、 10 、 11 、 12 里就没有了。尽管如此，这个问题仍然有一个秒杀解。你能多快想到？答案就是 1000 。首先， 0 和 4000 都是满足要求的数，因而我们不去看 1 到 4000 中有多少个满足要求的数，转而去看 0 到 3999 中有多少个满足要求的数，这对答案不会有影响。注意到，如果固定了末三位，比如说 618 ，那么在 0618 、 1618 、 2618 、 3618 这四个数中，有且仅有一个数满足，其各位数字之和能被 4 整除。考虑从 000 到 999 这 1000 个可能的末三位组合，每一个组合都唯一地对应了一个满足要求的四位数，因此问题的答案就是 1000 。真正有趣的事情在后面呢。一个小朋友举手说：“老师，我明白了，按照这个道理，从 1 到 3000 里各位数字之和能被 3 整除的数也是 1000 个。”另一个小朋友说：“废话，各位数字之和能被 3 整除就表明整个数能被 3 整除，在 1 到 3000 里这样的数当然有 1000 个嘛！”全班哄堂大笑。以上是在看见的解答方法。但我想到了一个更“秒杀”的方法。能被4整除的肯定能被2整除，1-4000中各位数字之和能够被2整除的数有4000/2=2000个（思考一下，为什么？设一个数为n,那么n+1与n之间，必有一个各位数字之和能被2整除。例如123与124之间，只有123的各位数字之和1+2+3=6能够被2整除)。这2000个数里面能再被2整除的有2000/2=1000个。所以1-4000里能被4整除的也是1000个。有人也许会问，上面这个方法之中，既然各位数字之和能被4整除的数的分布是不均匀的，那为什么各位数字之和能被2整除的数又是均匀的呢？另外，既然各位数字之和能被4整除的数是不均匀的，我们上面说过了，9 、 10 、 11 、 12四个数之间，没有满足题意的数字，那么有没有哪四个数字中有大于1个数的各位数字之和能被4整除呢？（也就是满足该题的答案在哪些数字之间的分布是密集的？）显然，一个数各位数字之和不是奇数就是偶数，所以各位数字之和能被2整除的数分布肯定是均匀的，可以直接除。但是各位数字之和能被4整除的数是不均匀的，例如在9 、 10 、 11 、 12四个数之间，没有满足题意的数字，但是39和40之间两个数都满足题意。显然，这是由于受到十进制满十进一的影响，导致各位数字之和的变化不均匀。作为一个计算机爱好者，我们甚至可以通过编程序查找出所有满足题意的解。以下是一段C语言程序，用来查找本题所有满足题意的数字。#includevoid main()int i,j,i1,i2,i3,i4;for(i=1;i=4000;i+) /枚举4000个数i1=i/1000; /求这个数的千位数字i2=i/100-10*i1;/求这个数的百位数字i3=(i/10); /求这个数的十位数字i4=i; /求这个数的个位数字j=i1+i2+i3+i4; /求各个位上的数字之和if(j%4=0)printf(%d ,i); /如果各个位上的数字之和能被四整除，则输出这个数字同理，我们只需要作一点修改，就能求出各个位上的数字之和能被四整除的数字的累计数#includevoid main()int i,j,i1,i2,i3,i4,s=0;for(i=1;i=4000;i+)i1=i/1000;i2=i/100-10*i1;i3=(i/10);i4=i;j=i1+i2+i3+i4;if(j%4=0)s+; /如果各个位上的数字之和能被四整除，则变量s累加1printf(s=%dn,s);/输出变量s显然，S=1000。所有满足题意的数字如下:0 4 8 13 17 22 26 31 35 39 40 44 48 53 57 62 66 71 75 79 80 84 88 93 97 103 107112 116 121 125 129 130 134 138 143 147 152 156 161 165 169 170 174 178 183 187192 196 202 206 211 215 219 220 224 228 233 237 242 246 251 255 259 260 264 268273 277 282 286 291 295 299 301 305 309 310 314 318 323 327 332 336 341 345 349350 354 358 363 367 372 376 381 385 389 390 394 398 400 404 408 413 417 422 426431 435 439 440 444 448 453 457 462 466 471 475 479 480 484 488 493 497 503 507512 516 521 525 529 530 534 538 543 547 552 556 561 565 569 570 574 578 583 587592 596 602 606 611 615 619 620 624 628 633 637 642 646 651 655 659 660 664 668673 677 682 686 691 695 699 701 705 709 710 714 718 723 727 732 736 741 745 749750 754 758 763 767 772 776 781 785 789 790 794 798 800 804 808 813 817 822 826831 835 839 840 844 848 853 857 862 866 871 875 879 880 884 888 893 897 903 907912 916 921 925 929 930 934 938 943 947 952 956 961 965 969 970 974 978 983 987992 996 1003 1007 1012 1016 1021 1025 1029 1030 1034 1038 1043 1047 1052 1056 1061 1065 1069 1070 1074 1078 1083 1087 1092 1096 1102 1106 1111 1115 1119 1120 1124 1128 1133 1137 1142 1146 1151 1155 1159 1160 1164 1168 1173 1177 1182 1186 1191 1195 1199 1201 1205 1209 1210 1214 1218 1223 1227 1232 1236 1241 1245 1249 1250 1254 1258 1263 1267 1272 1276 1281 1285 1289 1290 1294 1298 1300 1304 1308 1313 1317 1322 1326 1331 1335 1339 1340 1344 1348 1353 1357 1362 1366 1371 1375 1379 1380 1384 1388 1393 1397 1403 1407 1412 1416 1421 1425 1429 1430 1434 1438 1443 1447 1452 1456 1461 1465 1469 1470 1474 1478 1483 1487 1492 1496 1502 1506 1511 1515 1519 1520 1524 1528 1533 1537 1542 1546 1551 1555 1559 1560 1564 1568 1573 1577 1582 1586 1591 1595 1599 1601 1605 1609 1610 1614 1618 1623 1627 1632 1636 1641 1645 1649 1650 1654 1658 1663 1667 1672 1676 1681 1685 1689 1690 1694 1698 1700 1704 1708 1713 1717 1722 1726 1731 1735 1739 1740 1744 1748 1753 1757 1762 1766 1771 1775 1779 1780 1784 1788 1793 1797 1803 1807 1812 1816 1821 1825 1829 1830 1834 1838 1843 1847 1852 1856 1861 1865 1869 1870 1874 1878 1883 1887 1892 1896 1902 1906 1911 1915 1919 1920 1924 1928 1933 1937 1942 1946 1951 1955 1959 1960 1964 1968 1973 1977 1982 1986 1991 1995 1999 2002 2006 2011 2015 2019 2020 2024 2028 2033 2037 2042 2046 2051 2055 2059 2060 2064 2068 2073 2077 2082 2086 2091 2095 2099 2101 2105 2109 2110 2114 2118 2123 2127 2132 2136 2141 2145 2149 2150 2154 2158 2163 2167 2172 2176 2181 2185 2189 2190 2194 2198 2200 2204 2208 2213 2217 2222 2226 2231 2235 2239 2240 2244 2248 2253 2257 2262 2266 2271 2275 2279 2280 2284 2288 2293 2297 2303 2307 2312 2316 2321 2325 2329 2330 2334 2338 2343 2347 2352 2356 2361 2365 2369 2370 2374 2378 2383 2387 2392 2396 2402 2406 2411 2415 2419 2420 2424 2428 2433 2437 2442 2446 2451 2455 2459 2460 2464 2468 2473 2477 2482 2486 2491 2495 2499 2501 2505 2509 2510 2514 2518 2523 2527 2532 2536 2541 2545 2549 2550 2554 2558 2563 2567 2572 2576 2581 2585 2589 2590 2594 2598 2600 2604 2608 2613 2617 2622 2626 2631 2635 2639 2640 2644 2648 2653 2657 2662 2666 2671 2675 2679 2680 2684 2688 2693 2697 2703 2707 2712 2716 2721 2725 2729 2730 2734 2738 2743 2747 2752 2756 2761 2765 2769 2770 2774 2778 2783 2787 2792 2796 2802 2806 2811 2815 2819 2820 2824 2828 2833 2837 2842 2846 2851 2855 2859 2860 2864 2868 2873 2877 2882 2886 2891 2895 2899 2901 2905 2909 2910 2914 2918 2923 2927 2932 2936 2941 2945 2949 2950 2954 2958 2963 2967 2972 2976 2981 2985 2989 2990 2994 2998 3001 3005 3009 3010 3014 3018 3023 3027 3032 3036 3041 3045 3049 3050 3054 3058 3063 3067 3072 3076 3081 3085 3089 3090 3094 3098 3100 3104 3108 3113 3117 3122 3126 3131 3135 3139 3140 3144 3148 3153 3157 3162 3166 3171 3175 3179 3180 3184 3188 3193 3197 3203 3207 3212 3216 3221 3225 3229 3230 3234 3238 3243 3247 3252 3256 3261 3265 3269 3270 3274 3278 3283 3287 3292 3296 3302 3306 3311 3315 3319 3320 3324 3328 3333 3337 3342 3346 3351 3355 3359 3360 3364 3368 3373 3377 3382 3386 3391 3395 3399 3401 3405 3409 3410 3414 3418 3423 3427 3432 3436 3441 3445 3449 3450 3454 3458 3463 3467 3472 3476 3481 3485 3489 3490