100位平方数和立方数

liangbch

预备知识 举例。 举例 10位数字，第一位为0的完全平方数 01000,00000= 10000^2 01000,20001= 10001^2 01000,40004= 10002^2 01000,60009= 10003^2 01000,80016= 10004^2 01001,00025= 10005^2 10位数字，第一位不为0的完全平方数 10000,14129= 31623^2 10000,77376= 31624^2 10001,40625= 31625^2

wayne

要不这么考虑吧 平方数的末尾一位数只可能是0，1，4，6，9 末尾两位数只可能有22种， {00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96} 末尾三位数只可能有158种： {001, 004, 009, 016, 024, 025, 036, 041, 044, 049, 056, 064, 076, 081, 084, 089, 096, 100, 104, 116, 121, 124, 129, 136, 144, 156, 161, 164, 169, 176, 184, 196, 201, 204, 209, 216, 224, 225, 236, 241, 244, 249, 256, 264, 276, 281, 284, 289, 296, 304, 316, 321, 324, 329, 336, 344, 356, 361, 364, 369, 376, 384, 396, 400, 401, 404, 409, 416, 424, 436, 441, 444, 449, 456, 464, 476, 481, 484, 489, 496, 500, 504, 516, 521, 524, 529, 536, 544, 556, 561, 564, 569, 576, 584, 596, 600, 601, 604, 609, 616, 624, 625, 636, 641, 644, 649, 656, 664, 676, 681, 684, 689, 696, 704, 716, 721, 724, 729, 736, 744, 756, 761, 764, 769, 776, 784, 796, 801, 804, 809, 816, 824, 836, 841, 844, 849, 856, 864, 876, 881, 884, 889, 896, 900, 904, 916, 921, 924, 929, 936, 944, 956, 961, 964, 969, 976, 984, 996}

wayne

末尾四位数只可能由1019种： {1, 4, 9, 16, 25, 36, 41, 49, 64, 81, 84, 89, 96, 100, 116, 121, 129, \ 144, 161, 164, 169, 196, 201, 209, 224, 225, 241, 249, 256, 276, 281, \ 289, 304, 321, 324, 329, 336, 356, 361, 369, 384, 400, 401, 404, 409, \ 416, 436, 441, 449, 464, 481, 484, 489, 496, 516, 521, 529, 544, 561, \ 564, 569, 576, 596, 601, 609, 624, 625, 641, 644, 649, 656, 676, 681, \ 689, 704, 721, 724, 729, 736, 756, 761, 769, 784, 801, 804, 809, 816, \ 836, 841, 849, 864, 881, 889, 896, 900, 916, 921, 929, 944, 961, 964, \ 969, 976, 996, 1001, 1009, 1024, 1025, 1041, 1044, 1049, 1056, 1081, \ 1089, 1104, 1121, 1124, 1129, 1136, 1156, 1161, 1169, 1184, 1201, \ 1204, 1209, 1216, 1225, 1236, 1241, 1249, 1264, 1281, 1284, 1289, \ 1296, 1316, 1321, 1329, 1344, 1361, 1364, 1369, 1376, 1396, 1401, \ 1409, 1424, 1441, 1444, 1449, 1476, 1481, 1489, 1504, 1521, 1524, \ 1529, 1536, 1556, 1561, 1569, 1584, 1600, 1601, 1604, 1609, 1616, \ 1636, 1641, 1649, 1664, 1681, 1684, 1689, 1696, 1716, 1721, 1729, \ 1744, 1761, 1764, 1769, 1776, 1796, 1801, 1809, 1824, 1841, 1844, \ 1849, 1856, 1876, 1881, 1889, 1904, 1921, 1924, 1929, 1936, 1956, \ 1961, 1969, 2001, 2009, 2016, 2025, 2036, 2041, 2049, 2064, 2081, \ 2084, 2089, 2096, 2100, 2116, 2121, 2129, 2144, 2161, 2164, 2169, \ 2176, 2196, 2201, 2209, 2224, 2225, 2241, 2244, 2249, 2256, 2276, \ 2281, 2289, 2304, 2321, 2324, 2329, 2336, 2356, 2361, 2369, 2384, \ 2400, 2401, 2404, 2409, 2416, 2436, 2441, 2449, 2464, 2481, 2484, \ 2489, 2496, 2500, 2516, 2521, 2529, 2544, 2561, 2564, 2569, 2576, \ 2596, 2601, 2609, 2624, 2641, 2644, 2649, 2656, 2676, 2681, 2689, \ 2721, 2724, 2729, 2736, 2756, 2761, 2769, 2784, 2801, 2804, 2809, \ 2816, 2836, 2841, 2849, 2864, 2881, 2884, 2889, 2896, 2900, 2921, \ 2929, 2944, 2961, 2964, 2969, 2976, 2996, 3001, 3009, 3024, 3025, \ 3041, 3044, 3049, 3056, 3076, 3081, 3089, 3104, 3121, 3124, 3129, \ 3156, 3161, 3169, 3184, 3201, 3204, 3209, 3216, 3225, 3236, 3241, \ 3249, 3264, 3281, 3284, 3289, 3296, 3316, 3321, 3329, 3344, 3361, \ 3369, 3376, 3396, 3401, 3409, 3424, 3441, 3444, 3449, 3456, 3476, \ 3481, 3489, 3504, 3521, 3524, 3529, 3536, 3556, 3561, 3569, 3584, \ 3600, 3601, 3604, 3609, 3616, 3636, 3641, 3649, 3664, 3681, 3684, \ 3689, 3696, 3716, 3721, 3729, 3744, 3761, 3764, 3769, 3776, 3796, \ 3801, 3809, 3824, 3841, 3844, 3849, 3856, 3876, 3881, 3889, 3904, \ 3921, 3924, 3929, 3936, 3956, 3961, 3969, 3984, 4001, 4004, 4009, \ 4025, 4036, 4041, 4049, 4064, 4081, 4084, 4089, 4096, 4100, 4116, \ 4121, 4129, 4144, 4161, 4164, 4169, 4176, 4196, 4201, 4209, 4225, \ 4241, 4244, 4249, 4256, 4276, 4281, 4289, 4304, 4321, 4324, 4329, \ 4336, 4361, 4369, 4384, 4400, 4401, 4404, 4409, 4416, 4436, 4441, \ 4449, 4464, 4481, 4484, 4489, 4496, 4516, 4521, 4529, 4544, 4561, \ 4564, 4569, 4576, 4596, 4601, 4609, 4624, 4641, 4644, 4649, 4656, \ 4676, 4681, 4689, 4704, 4721, 4724, 4729, 4736, 4756, 4761, 4769, \ 4784, 4801, 4804, 4809, 4816, 4836, 4841, 4849, 4864, 4881, 4884, \ 4889, 4900, 4916, 4921, 4929, 4961, 4964, 4969, 4976, 5001, 5009, \ 5024, 5025, 5041, 5044, 5049, 5056, 5076, 5081, 5089, 5104, 5121, \ 5124, 5129, 5136, 5156, 5161, 5169, 5184, 5201, 5204, 5209, 5216, \ 5225, 5236, 5241, 5249, 5264, 5281, 5284, 5289, 5296, 5316, 5321, \ 5329, 5344, 5361, 5364, 5369, 5376, 5396, 5401, 5409, 5424, 5441, \ 5444, 5449, 5456, 5476, 5481, 5489, 5504, 5521, 5524, 5529, 5536, \ 5556, 5561, 5569, 5584, 5600, 5601, 5604, 5609, 5616, 5625, 5636, \ 5641, 5649, 5664, 5681, 5684, 5689, 5696, 5716, 5721, 5729, 5744, \ 5761, 5764, 5769, 5776, 5796, 5801, 5809, 5824, 5841, 5844, 5849, \ 5856, 5876, 5881, 5889, 5904, 5921, 5924, 5929, 5936, 5956, 5961, \ 5969, 5984, 6001, 6004, 6009, 6016, 6025, 6041, 6049, 6064, 6081, \ 6084, 6089, 6096, 6100, 6116, 6121, 6129, 6144, 6161, 6164, 6169, \ 6176, 6196, 6201, 6209, 6224, 6225, 6241, 6244, 6249, 6256, 6276, \ 6281, 6289, 6304, 6321, 6324, 6329, 6356, 6361, 6369, 6384, 6400, \ 6401, 6404, 6409, 6416, 6436, 6441, 6449, 6464, 6481, 6484, 6489, \ 6496, 6516, 6521, 6529, 6544, 6561, 6564, 6569, 6576, 6596, 6601, \ 6609, 6624, 6641, 6644, 6649, 6656, 6676, 6681, 6689, 6704, 6721, \ 6724, 6729, 6736, 6756, 6761, 6769, 6784, 6801, 6804, 6809, 6816, \ 6836, 6841, 6849, 6864, 6881, 6884, 6889, 6896, 6900, 6916, 6921, \ 6929, 6944, 6961, 6964, 6969, 6976, 6996, 7001, 7009, 7024, 7025, \ 7041, 7044, 7049, 7056, 7076, 7081, 7089, 7104, 7121, 7124, 7129, \ 7136, 7156, 7161, 7169, 7184, 7201, 7204, 7209, 7216, 7225, 7236, \ 7241, 7249, 7264, 7281, 7284, 7289, 7296, 7316, 7321, 7329, 7344, \ 7361, 7364, 7369, 7376, 7396, 7401, 7409, 7424, 7441, 7444, 7449, \ 7456, 7476, 7481, 7489, 7504, 7521, 7524, 7529, 7536, 7556, 7561, \ 7569, 7584, 7600, 7601, 7604, 7609, 7616, 7636, 7641, 7649, 7664, \ 7681, 7684, 7689, 7696, 7716, 7721, 7729, 7744, 7761, 7764, 7769, \ 7776, 7796, 7801, 7809, 7824, 7841, 7844, 7849, 7856, 7876, 7881, \ 7889, 7904, 7921, 7929, 7936, 7956, 7961, 7969, 7984, 8001, 8004, \ 8009, 8016, 8025, 8036, 8041, 8049, 8081, 8084, 8089, 8096, 8100, \ 8116, 8121, 8129, 8144, 8161, 8164, 8169, 8176, 8196, 8201, 8209, \ 8224, 8225, 8241, 8244, 8249, 8256, 8276, 8281, 8289, 8304, 8321, \ 8324, 8329, 8336, 8356, 8361, 8369, 8384, 8400, 8401, 8404, 8409, \ 8416, 8436, 8441, 8449, 8464, 8481, 8484, 8489, 8496, 8516, 8521, \ 8529, 8561, 8564, 8569, 8576, 8596, 8601, 8609, 8624, 8641, 8644, \ 8649, 8656, 8676, 8681, 8689, 8704, 8721, 8724, 8729, 8736, 8756, \ 8761, 8769, 8784, 8801, 8804, 8809, 8816, 8836, 8841, 8849, 8864, \ 8881, 8884, 8889, 8896, 8900, 8916, 8921, 8929, 8944, 8961, 8964, \ 8969, 8976, 8996, 9001, 9009, 9024, 9025, 9041, 9044, 9049, 9056, \ 9076, 9081, 9089, 9104, 9121, 9124, 9129, 9136, 9156, 9161, 9169, \ 9184, 9201, 9204, 9209, 9216, 9225, 9236, 9241, 9249, 9264, 9281, \ 9289, 9296, 9316, 9321, 9329, 9344, 9361, 9364, 9369, 9376, 9396, \ 9401, 9409, 9424, 9441, 9444, 9449, 9456, 9476, 9481, 9489, 9504, \ 9521, 9524, 9529, 9536, 9561, 9569, 9584, 9600, 9601, 9604, 9609, \ 9616, 9636, 9641, 9649, 9664, 9681, 9684, 9689, 9696, 9716, 9721, \ 9729, 9744, 9761, 9764, 9769, 9776, 9796, 9801, 9809, 9824, 9841, \ 9844, 9849, 9856, 9876, 9881, 9889, 9904, 9921, 9924, 9929, 9936, \ 9956, 9961, 9969, 9984}

medie2005

wayne的方法并不能减少多少计算量。

wayne

是啊，我也发现了

northwolves

复杂度分析，50个数字的所有排列为，若加上限制条件，前50位数中，每个数字最多出现10次，则实际排列数可大大降低，我不知道这个数是多少: 1018872811

northwolves

(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^10)^10=1+10x+55x^2+220x^3+715x^4+2002x^5+5005x^6+11440x^7+24310x^8+48620x^9+92378x^10+167950x^11+293830x^12+496870x^13+814990x^14+1300354x^15+2022955x^16+3074500x^17+4572425x^18+6663800x^19+9528805x^20+13383370x^21+18480520x^22+25109950x^23+33595375x^24+44289256x^25+57564595x^26+73803620x^27+93383345x^28+116658190x^29+143940082x^30+175476730x^31+211429075x^32+251849140x^33+296659645x^34+345636808x^35+398397725x^36+454393610x^37+512909980x^38+573074590x^39+633873559x^40+694175680x^41+752764375x^42+808376140x^43+859743835x^44+905642810x^45+944937620x^46+976626970x^47+999884545x^48+1014093520x^49+1018872811x^50+1014093520x^51+999884545x^52+976626970x^53+944937620x^54+905642810x^55+859743835x^56+808376140x^57+752764375x^58+694175680x^59+633873559x^60+573074590x^61+512909980x^62+454393610x^63+398397725x^64+345636808x^65+296659645x^66+251849140x^67+211429075x^68+175476730x^69+143940082x^70+116658190x^71+93383345x^72+73803620x^73+57564595x^74+44289256x^75+33595375x^76+25109950x^77+18480520x^78+13383370x^79+9528805x^80+6663800x^81+4572425x^82+3074500x^83+2022955x^84+1300354x^85+814990x^86+496870x^87+293830x^88+167950x^89+92378x^90+48620x^91+24310x^92+11440x^93+5005x^94+2002x^95+715x^96+220x^97+55x^98+10x^99+x^100

liangbch

26# northwolves 这么小，对结果表示怀疑，希望给出说明。

northwolves

26# northwolves 这么小，对结果表示怀疑，希望给出说明。 liangbch 发表于 2010-1-22 00:20

计算错误,是排列不是组合

northwolves

不过最大数应该是这个形式吧:9999999999*