#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
int m , phiM , rst;

void findRst()
{
    int i , j , k , sqrtPhiM , md , tmpI , tmp10;
    sqrtPhiM = ( int )( sqrt( ( double ) phiM ) + 1e-6 );
    for( i = 1; i <= sqrtPhiM; ++i ){
        tmpI = i , tmp10 = 10;
        if( phiM % tmpI == 0 ){
            md = 1;
            while( tmpI ){
                if( tmpI & 1 ){
                    md = ( ( long long ) ( md  ) * ( tmp10 ) ) % m;
                    }
                tmpI >>= 1;
                tmp10 = ( ( long long ) tmp10 * tmp10 ) % m;
            }
            if( md == 1 ) { rst = i ; return;}
        }
    }
    for( i = sqrtPhiM ; i >= 1; --i )
            if( phiM % i == 0 ){
            tmpI = phiM / i , tmp10 = 10;
            if( phiM % tmpI == 0 ){
                md = 1;
                while( tmpI ){
                    if( tmpI & 1 )
                        md = ( ( long long ) ( md  ) * ( tmp10 ) ) % m;
                    tmpI >>= 1;
                    tmp10 = ( ( long long ) tmp10 * tmp10 ) % m;
                }
                if( md == 1 ) { rst = phiM / i ; return;}
            }
        }
    while( 1 );
}


int main()
{
    int i , j , k , iCase, nCase , sqrtM;
    for( iCase = 0; scanf( "%d" , &m ) != EOF && m > 0 ; ++iCase ){
        printf( "Case %d: " , iCase + 1 );
        for( i = 0;  m % 2 == 0 && i < 3; ++i ){
            m /= 2;
        }
        if( m % 2 == 0 || m % 5 == 0 ){
            printf( "0\n" );
            continue;
        }
        phiM = m;
        if( m == 1 ) { printf( "1\n" ); continue; }
        sqrtM = (int )( sqrt( ( double )m ) + 1e-5 );
        for( i = 2; i <= sqrtM; ++i )
            if( i != 3 ){
                if( m % i == 0 ){
                    while( m % i == 0 )
                        m /= i;
                    phiM = phiM / i * ( i - 1 );
                }
            }
        if( m % 3 == 0 ){
            phiM *= 6;
        }
        else if ( m != 1 ){
            phiM = m - 1;
        }
        findRst();
        printf( "%d\n" , rst );
    }
}

    
        
        
                
                    
            

    

• md = ( ( long long ) ( md ) * ( tmp10 ) ) % m; (19) zfy0701 2008-10-06 21:39:48
  • Re:md = ( ( long long ) ( md ) * ( tmp10 ) ) % m; (38) wxnfifth 2008-10-06 21:47:20
    • Re:(a*b)%c=((a%c)*(b%c))%c; (19) MasterLuo 2008-10-06 21:53:50
      • one possible solution (164) zfy0701 2008-10-06 21:58:44