猜猜我的手机号码？

gxqcn

如果在已知：前三位为189，末两位为43，11个数字分别为：01123456789，且为两个素数之积，其中一素数为5位数。 则存在一些快速算法，比如说： 1、根据末两位为43，且为两素数之积，可先建立100内正奇数的乘法表，筛选出积末两位为43者的组合； 2、可先建立素数表，范围为：10000～1899999； 3、试算时，在确定一素数后，可以马上确定出另一素数的取值范围； 4、在计算出两素数乘积（需64位存储）后，可以马上减去18900000043，这样仅保留中间的6位数字，可以用DWORD类型数据存储； 5、在统计数字字符时，需要将数字转化为10进制字符，此处有些快速算法，可完全避免除法指令进行提速；或将012567六个数字全排列后排序，而后进行二分查找判定。

〇〇

31# gxqcn 请提供一个代码吧 我的代码已经用到了你的若干建议

gxqcn

具体代码我不想写了，结果应该在秒级内输出。

〇〇

具体代码我不想写了，结果应该在秒级内输出。 gxqcn 发表于 2009-8-25 13:04

我用30楼代码 if( temp>189e8 && temp<190e8 )还是9秒，不知道什么时候限制1出现2次 medie2005 的最大时间耗费是什么，int64的mod /运算？ 你的建议中最大缩短时间是靠什么？

gxqcn

下面的代码，用了 STL，还调用了 HugeCalc 以快速生成素数表及统计耗时：

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
5. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
7. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
8. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
11. int main(int argc, char* argv[])
12. {
13. // printf("Hello World!\n");
15. cout << "Call " << HugeCalc::GetVer() << endl << endl;
17. // 初始化
18. HugeCalc::EnableTimer( TRUE );
19. HugeCalc::ResetTimer();
21. UINT32 i, j;
22. UINT32 u32Size = HugeCalc::GetPrimeCount( 10000, 1899999 );
23. UINT32 * pPrimeBuffer = new UINT32[u32Size];
24. HugeCalc::GetPrimeList( pPrimeBuffer, u32Size, 10000, 1899999 );
26. UINT32 LUT[720], u32Dights[6] = { 0, 1, 2, 5, 6, 7 };
27. UINT32 *p, *p1, *p2, *p_end;
29. *( p = LUT ) = 1256743; /* 012567 43 */
30. while( next_permutation( u32Dights, u32Dights+6 ))
31. {
32. for ( i=0, j=0; 6!=j; ++j )
33. {
34. i = i * 10 + u32Dights[j];
35. }
36. *(++p) = i * 100 + 43;
37. }
39. p1 = pPrimeBuffer;
40. do
41. {
42. p2 = lower_bound( p1, pPrimeBuffer + u32Size, (UINT32)((UINT64)18901256743 / *p1 ));
43. p_end = lower_bound( p2, pPrimeBuffer + u32Size, (UINT32)((UINT64)18976521043 / *p1 )+1 );
45. do
46. {
47. i = (UINT32)( UInt32x32To64( *p1, *p2 ) - (UINT64)18900000000 );
48. p = lower_bound( LUT, LUT+720, i );
50. if ( LUT+720 != p && i == *p )
51. {
52. cout << ((*p>=10000000)?"189":"1890") << *p << " = " << *p1 << " * " << *p2 << endl;
53. }
54. }while( p_end != ++p2 );
56. } while( *(++p1) <= 99999 );
58. delete []pPrimeBuffer;
60. HugeCalc::EnableTimer( FALSE );
62. cout << endl << "耗时为：" << HugeCalc::GetTimerStr( FT_DOT06SEC_s ) << endl;
64. return 0;
65. }

复制代码

请将上述代码复制粘贴进 [..]\CopyrightByGuoXianqiang\HugeCalc\testDLL\src\ANSI_C++\ansi_c++.cpp，然后编译运行即可。 它运行速度非常快，结果如下：

1. Call HugeCalc V8.1.0.0 (Win32)
3. 18962715043 = 11173 * 1697191
4. 18960217543 = 13037 * 1454339
5. 18927156043 = 13187 * 1435289
6. 18952607143 = 13291 * 1425973
7. 18967512043 = 13799 * 1374557
8. 18926501743 = 13841 * 1367423
9. 18957201643 = 15077 * 1257359
10. 18962107543 = 16223 * 1168841
11. 18965210743 = 16631 * 1140353
12. 18950726143 = 17123 * 1106741
13. 18907561243 = 20357 * 928799
14. 18965710243 = 21023 * 902141
15. 18917062543 = 21817 * 867079
16. 18927615043 = 21893 * 864551
17. 18967102543 = 22247 * 852569
18. 18920516743 = 25183 * 751321
19. 18901652743 = 26501 * 713243
20. 18910725643 = 28657 * 659899
21. 18927610543 = 28807 * 657049
22. 18912076543 = 29269 * 646147
23. 18910765243 = 29569 * 639547
24. 18912576043 = 33773 * 559991
25. 18927160543 = 34351 * 550993
26. 18961270543 = 34367 * 551729
27. 18976105243 = 36527 * 519509
28. 18965172043 = 37309 * 508327
29. 18925160743 = 41981 * 450803
30. 18910625743 = 42131 * 448853
31. 18927016543 = 46171 * 409933
32. 18921567043 = 46867 * 403729
33. 18927561043 = 49463 * 382661
34. 18951207643 = 52201 * 363043
35. 18902756143 = 56893 * 332251
36. 18970162543 = 66509 * 285227
37. 18921675043 = 66571 * 284233
38. 18917065243 = 70957 * 266599
39. 18950126743 = 76603 * 247381
40. 18925671043 = 83101 * 227743
41. 18907652143 = 87049 * 217207
42. 18916705243 = 95891 * 197273
43. 18957062143 = 99023 * 191441
45. 耗时为：0.174513 s
46. Press any key to continue

复制代码

mathe

对于gxqcn的这个问题,总共才6!=720个候选数,我觉得直接因子分解它们可能会更加快

medie2005

分解用费马法即可.

mathe

其实这里试除也就可以了

mathe

用LiDIA写了个程序,不过发现速度不快6秒.这个应该是使用通用的因子分解算法的问题:

2. #include "LiDIA/bigint.h"
3. #include "LiDIA/rational_factorization.h"
4. #include <algorithm>
5. using namespace std;
6. using namespace LiDIA;
8. static int digitss[6]={0,1,2,5,6,7};
10. int main()
11. {
12. int i,j;
13. long long r;
14. bigint v=1890;
15. v*=10000000;
16. do{
17. for(i=0,j=0;j!=6;j++){
18. i=i*10+digitss[j];
19. }
20. i=i*100+43;
21. bigint b=v+i;
22. rational_factorization fr(b);
23. fr.factor(3);
24. if(fr.no_of_comp()==2){
25. for(j=0;j<2;j++){
26. if(fr.exponent(j)!=1)
27. break;
28. }
29. if(j==2){
30. bigint v1=fr.base(0);
31. bigint v2=fr.base(1);
32. if(v1>=10000&&v1<=10000000&&v2>=10000&&v2<=10000000){
33. int u1,u2;
34. v1.intify(u1);v2.intify(u2);
35. printf("189%08d=%d*%d\n",i,u1,u2);
36. }
37. }
38. }
39. }while(next_permutation(digitss,digitss+6));
40. }

复制代码

不过结果有46个,同gxqcn不完全相同 18901652743=26501*713243 18902756143=56893*332251 18907561243=20357*928799 18907652143=87049*217207 18910625743=42131*448853 18910725643=28657*659899 18910765243=29569*639547 18912065743=111521*169583 18912076543=29269*646147 18912576043=33773*559991 18916705243=95891*197273 18917062543=21817*867079 18917065243=70957*266599 18920516743=25183*751321 18920716543=108947*173669 18921567043=46867*403729 18921675043=66571*284233 18925160743=41981*450803 18925671043=83101*227743 18926501743=13841*1367423 18927016543=46171*409933 18927156043=13187*1435289 18927160543=34351*550993 18927561043=49463*382661 18927610543=28807*657049 18927615043=21893*864551 18950126743=76603*247381 18950621743=121139*156437 18950726143=17123*1106741 18951207643=52201*363043 18952607143=13291*1425973 18957062143=99023*191441 18957201643=15077*1257359 18960217543=13037*1454339 18961027543=109507*173149 18961270543=34367*551729 18962107543=16223*1168841 18962715043=11173*1697191 18965172043=37309*508327 18965210743=16631*1140353 18965710243=21023*902141 18967102543=22247*852569 18967512043=13799*1374557 18970162543=66509*285227 18972506143=112501*168643 18976105243=36527*519509

gxqcn

我的结果与 22# medie2005 的一致。 mathe 漏了一个限定条件：其中一个素因子为5位数。 虽然候选数不多，但试乘法比因子分解法效率高得多，所以我一开始就偏向于用试算法。