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*