- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 3751
- 在线时间
- 小时
|
楼主 |
发表于 2008-12-24 15:13:32
|
显示全部楼层
代码：- #include <cstdlib>
- #include <iostream>
- #include <cmath>
- #include "gmp.h"
- using namespace std;
- const int L=40000;
- mpz_t Hash[L][10];
- mpz_t number[L];
- mpz_t POW10[100];
- void Init( ){
- mpz_init_set_ui( Hash[0][0], 0 );
- for( unsigned i=1; i<L; ++i ) mpz_init_set_ui( Hash[i][0], 1 );
- for( i=0; i<L; ++i ){
- mpz_init_set_ui( number[i], 0 );
- for( unsigned j=1; j<10; ++j ){
- mpz_init( Hash[i][j] );
- mpz_mul_ui( Hash[i][j], Hash[i][j-1], i );
- }
- }
- mpz_init_set_ui( POW10[0], 1 );
- for( i=1; i<100; ++i ){
- mpz_init( POW10[i] );
- mpz_mul_ui( POW10[i], POW10[i-1], 10 );
- }
- }
- void Set_num_0( unsigned n ){
- for( int i=0; i<L; ++i )
- mpz_set_ui( number[i], n );
- }
- void Clean( ){
- for( unsigned i=0; i<L; ++i ){
- mpz_clear( number[i] );
- for( unsigned j=0; j<10; ++j )
- mpz_clear( Hash[i][j] );
- }
- for( i=0; i<100; ++i )
- mpz_clear( POW10[i] );
- }
- bool check( mpz_t &n, int *list, int m ){
- int c[10]={0}, d[10]={0};
- for( int i=1; i<m+1; ++i ) c[list[i]]++;
- char str[100];
- mpz_get_str( str, 10, n );
- for( i=0; str[i]!='\0'; ++i ) d[str[i]-'0']++;
- for( i=0; i<10; ++i ) if( c[i]!=d[i] ) return false;
- return true;
- }
- void combination( unsigned n, unsigned m ){
- int *c=new int[m+2], j, *num=new int[m+2], g;
- for( j=1; j<=m; ++j ) c[j]=j-1, num[j]=c[j]-j+1;
- c[m+1]=n;
- int start=int(pow(10, (m-1)/9.0)/pow(m,1/9.0)), t=start;
- R2: //copy( num+1, num+m+1, ostream_iterator<int>(cout," ") ),cout<<endl;
- if( c[m-1]>m-1 ){
- if( mpz_cmp( number[2*t-1], POW10[m] )>0 ){
- for( start=t; start<2*t; ++start ){
- if( mpz_cmp( number[start], POW10[m] )>0 ) start=2*t+1;
- else
- if( check( number[start], num, m ) ){
- mpz_out_str( stdout, 10, number[start] );
- printf(" %d",start);
- if( mpz_probab_prime_p( number[start], 10 ) )
- printf(" prime!");
- printf("\n");
- }
- }
- }
- }
- if( m&1 )
- if( c[1]+1<c[2] ){
- for( g=t; g<2*t; ++g ){
- mpz_sub( number[g], number[g], Hash[g][num[1]] );
- }
- ++c[1], ++num[1];
- for( g=t; g<2*t; ++g ){
- mpz_add( number[g], number[g], Hash[g][num[1]] );
- }
- goto R2;
- }
- else{
- j=2; goto R4;
- }
- else
- if( c[1]>0 ){
- for( g=t; g<2*t; ++g ){
- mpz_sub( number[g], number[g], Hash[g][num[1]] );
- }
- --c[1], --num[1];
- for( g=t; g<2*t; ++g ){
- mpz_add( number[g], number[g], Hash[g][num[1]] );
- }
- goto R2;
- }
- else{
- j=2; goto R5;
- };
- R4: if( c[j]>=j ){
- for( g=t; g<2*t; ++g ){
- if( j<=m )
- mpz_sub( number[g], number[g], Hash[g][num[j]] );
- if( j-1<=m )
- mpz_sub( number[g], number[g], Hash[g][num[j-1]] );
- }
- c[j]=c[j-1], num[j]=c[j]-j+1; c[j-1]=j-2, num[j-1]=c[j-1]-(j-1)+1;
- for( g=t; g<2*t; ++g ){
- if( j<=m )
- mpz_add( number[g], number[g], Hash[g][num[j]] );
- if( j-1<=m )
- mpz_add( number[g], number[g], Hash[g][num[j-1]] );
- }
- goto R2;
- }
- else
- ++j;
- R5: if( c[j]+1<c[j+1] ){
- for( g=t; g<2*t; ++g ){
- if( j<=m )
- mpz_sub( number[g], number[g], Hash[g][num[j]] );
- if( j-1<=m )
- mpz_sub( number[g], number[g], Hash[g][num[j-1]] );
- }
- c[j-1]=c[j], num[j-1]=c[j-1]-(j-1)+1; c[j]=c[j]+1, num[j]=c[j]-j+1;
-
- for( g=t; g<2*t; ++g ){
- if( j<=m )
- mpz_add( number[g], number[g], Hash[g][num[j]] );
- if( j-1<=m )
- mpz_add( number[g], number[g], Hash[g][num[j-1]] );
- }
-
- goto R2;
- }
- else{
- ++j;
- if( j<=m ) goto R4;
- }
- delete []c;
- delete []num;
- }
- int main(int argc, char *argv[])
- {
- Init();
- for( unsigned i=3; i<=18; ++i ){
- Set_num_0( i );
- cout<<i<<" digits search start!\n";
- combination( i+9, i );
- }
- Clean( );
- cout<<"press any key to continue...\n";
- cin.get();
- return EXIT_SUCCESS;
- }
|
|
楼主: medie2005
IP卡
狗仔卡
显身卡
发表于 2008-12-24 19:45:06
