shuixianhua.rar_visual c

#include <cstdlib> #include <iostream> #include <windows.h> #include <cmath> #include "gmp.h" using namespace std; const int L=22; mpz_t Hash[10][L]; mpz_t dif[10][10][L]; mpz_t POW10[L]; char str[L<<1]; void Init( ){ unsigned i, j; for( i=0; i<10; ++i ){ for( j=0; j<L; ++j ) mpz_init( Hash[i][j] ); } mpz_set_ui( Hash[0][0], 0 ); mpz_init_set_ui( POW10[0], 1 ); for( i=1; i<10; ++i ) mpz_set_ui( Hash[i][0], 1 ); for( j=1; j<L; ++j ){ mpz_init( POW10[j] ); mpz_mul_ui( POW10[j], POW10[j-1], 10 ); } for( i=0; i<10; ++i ){ for( j=1; j<L; ++j ){ mpz_mul_ui( Hash[i][j], Hash[i][j-1], i ); } } for( int k=0; k<L; ++k ){ for( i=0; i<10; ++i ){ for( j=0; j<10; ++j ){ mpz_init( dif[i][j][k] ); mpz_sub( dif[i][j][k], Hash[i][k], Hash[j][k] ); } } } } void Clean( ){ unsigned i, j; for( i=0; i<10; ++i ) for( j=0; j<L; ++j ){ mpz_clear( Hash[i][j] ); } for( j=0; j<L; ++j ) mpz_clear( POW10[j] ); for( int k=0; k<L; ++k ){ for( i=0; i<10; ++i ){ for( j=0; j<10; ++j ){ mpz_clear( dif[i][j][k] ); } } } } bool check( mpz_t &n, int *c ){ int i, d[10]={0}; mpz_get_str( str, 10, n ); for( i=0; str[i]!='\0'; ++i ){ d[str[i]-'0']++; if( d[str[i]-'0']>c[str[i]-'0'] ) return false; } return true; } void combination( unsigned n, unsigned m ){ int *c=new int[m+2], j, *num=new int[m+2]; int dig[10]={0}; dig[0]=m; for( j=1; j<=m; ++j ) c[j]=j-1, num[j]=c[j]-j+1; c[m+1]=n; mpz_t number; mpz_init_set_ui( number, 0 ); R2: if( mpz_cmp( number, POW10[m-1] )>0 && mpz_cmp( number, POW10[m] )<0 && check( number, dig ) ){ mpz_out_str( stdout, 10, number ); printf("\n"); } if( m&1 ) if( c[1]+1<c[2] ){ --dig[num[1]]; mpz_add( number, number, dif[num[1]+1][num[1]][m] ); ++c[1], ++num[1]; ++dig[num[1]]; goto R2; } else{ j=2; goto R4; } else if( c[1]>0 ){ --dig[num[1]]; mpz_sub( number, number, dif[num[1]][num[1]-1][m] ); --c[1], --num[1]; ++dig[num[1]]; goto R2; } else{ j=2; goto R5; }; R4: if( c[j]>=j ){ if( j<=m ){ --dig[num[j]]; mpz_sub( number, number, dif[num[j]][c[j-1]-j+1][m] ); } if( j-1<=m ){ --dig[num[j-1]]; mpz_sub( number, number, dif[num[j-1]][0][m] ); } 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; if( j<=m ) ++dig[num[j]]; if( j-1<=m ) ++dig[num[j-1]]; goto R2; } else ++j; R5: if( c[j]+1<c[j+1] ){ if( j<=m ){ --dig[num[j]]; mpz_sub( number, number, dif[num[j]][c[j]+1-j+1][m] ); } if( j-1<=m ){ --dig[num[j-1]]; mpz_sub( number, number, dif[num[j-1]][c[j]-j+2][m] ); } 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; if( j<=m ) ++dig[num[j]]; if( j-1<=m ) ++dig[num[j-1]]; goto R2; } else{ ++j; if( j<=m ) goto R4; } delete []c; delete []num; mpz_clear( number ); } int main(int argc, char *argv[]) { int time=GetTickCount(); Init(); for( unsigned i=21; i<L; ++i ){ cout<<i<<" digits search start!\n"; combination( i+9, i ); } Clean( ); cout<<"time : "<<GetTickCount()-time<<" ms\n"; cout<<"press any key to continue...\n"; cin.get(); return EXIT_SUCCESS; }