Cod sursă (job #314910)

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int BASE = 1e4 ;

long long n ;


// a = b

void cpy ( int a [] , int b[] ){
    static int i ;

    for ( i = 0 ; i <= b [ 0 ] ; i ++ ){
        a [ i ] = b [ i ];
    }

}

//a = a * b ;
void prod ( int a[] , int b [] ){
    int temp [ 10 ] , t ;
    static int i , j ;

    memset ( temp , 0 , sizeof temp );
    temp [ 0 ] = a[ 0 ] + b [ 0 ] - 1 ;

    for ( i = 1 ; i <= a[ 0 ] ; i ++ ){
        for ( j = 1 ; j <= b [ 0 ] ; j++ ){
            temp [ i + j - 1 ] += a[ i ] * b[ j ] ;
        }
    }

    t = 0 ;
    for ( i = 1 ; i <= temp[ 0 ] ; i++ ){
        temp[ i ] += t ;
        t = temp [ i ] / BASE ;
        temp [ i ] %= BASE ;
    }

    if ( t ){
        temp [ ++temp [ 0 ] ] = t ;
    }

    cpy ( a , temp );

}

// a = a % MOD
void modulo ( int a [] , long long MOD ){
    static long long rest ;
    static int i ;

    rest = 0 ;
    for ( i = a [ 0 ] ; i ; i-- ){
        rest = ( rest * BASE + a [ i ] ) %MOD ;
    }

    i = 0 ;
    while ( rest ){
        a [ ++i ] = rest % BASE;
        rest /= BASE ;
    }
    a [ 0 ] = i ;

}

long long phi ( long long a ){
    long long i ;
    long long phi = a ;



    for ( i = 2 ; i * i <= a ; i++ ){

        if ( a % i == 0 ){
            phi = phi/i ;
            phi = phi * ( i -1 ) ;
        }

        while ( a % i == 0 ){
            a/=i ;
        }
    }
    if ( a - 1 ){
        phi = phi / a ;
        phi = phi * ( a -1 ) ;
    }

    return phi ;
}


long long logPower10 ( long long pow , long long MOD ){
    int p [ ] = { 1 , 1 , 0 , 0 , 0 , 0 , 0 };
    int a [ ] = { 1 , 10 , 0 , 0 , 0 , 0 , 0 };


    while ( pow ){

        if ( pow % 2 ){
            prod ( p , a );
            modulo( p , MOD );
        }

        prod( a , a );
        modulo( a , MOD );
        pow /= 2 ;
    }

    long long rest = 0 ;

    for ( int i = p [ 0 ] ; i  ; i-- ){
        rest = rest * BASE + p [ i ] ;
    }
    return rest  ;
}

int main(){
    long long tot , rest , i , j ;


    freopen("perioada.in","r",stdin);
    freopen("perioada.out","w",stdout);

    scanf("%lld",&n);

    tot = phi ( n );

    for ( i = 1 ; i * i <= tot ; i++ ){
        if ( tot % i == 0 ){
            rest = logPower10( i , n );
            if ( rest == 1 ){
                printf("%lld", i );
                return 0 ;
            }
        }
    }
    j = i ;
    for ( i = j - 1 ; i ; i-- ){
        long long d ;


        if ( tot % i == 0 ){
            rest = logPower10(  tot / i , n );
            if ( rest == 1 ){
                printf("%lld", tot/i );
                return 0 ;
            }
        }
    }


//    int a [ 5 ] ={ 1 , 3000 , 0 , 0 , 0};
//    int b [ 5 ] ={ 1 , 4000 , 0 , 0 , 0};
//
//    prod ( a , b );
//
//    modulo( a , 10000000 );

    return 0;
}