一个很无聊的题目，要注意负数的存在和溢出的问题。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1730
#include <stdio.h>
#include <math.h>

const int MAX = 50000;

int prime[MAX];

int number[MAX];

int find ( int n )
{
    
    
    number[0] = number[1] = 1;
    for ( int i=2; i<=n; i++ )
    {
        number[i] = 0;
    }
    
    for ( int j=2; j<=n; j++ )
    {
        for ( int z=j+j; z<=n; z+=j )
        {
            if ( ! number[z] )
            {
                number[z] = 1;
            }
        }
    }
    
    int p = 0;
    for ( i=0; i<=n; i++ )
    {
        if ( !number[i] )
        {
            prime[p++] = i;
        }
    }
    
    return p;
}

int num[MAX];
int pre;

int f ( __int64 n, int len )
{
    
    int l, r, mid;
    int flag = 1;
    
    int n2 = ( int )( sqrt ( (double)n ) ) + 1;
    
    l = 0;
    r = len - 1;
    while ( l<=r )
    {
        mid = ( l + r ) / 2;
        if ( prime[mid] > n2 )
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    
    for ( int i=0; i<=r; i++ )
    {
        if ( ! ( n % prime[i] ) )
        {
            flag = 0;
            while ( ! ( n % prime[i] ) )
            {
                num[pre++] = prime[i];
                n /= prime[i];
            }
            break;
        }
    }
    if ( flag )
    {
        num[pre++] = n;
        n = 1;
    }
    
    return n;
}

int gdc ( int a, int b )
{
    
    if ( a == 0 )
    {
        return b;
    }
    if ( b == 0 )
    {
        return a;
    }
    return gdc ( b, a % b );
}

int main ()
{
    
    __int64 n;
    int flag;
    
    int len = find ( MAX );
    while ( scanf ( "%I64d", &n ) != EOF && n )
    {
        __int64 temp = n;
        if ( n < 0 )
        {
            n = -n;
            flag = 1;
        }
        else
        {
            flag = 0;
        }
        pre = 0;
        while ( n != 1 )
        {
            n = f ( n, len );
        }
        
        int ans = -1;
        int count  = 1;
        for ( int i=0; i<pre-1; i++ )
        {
            if ( num[i] != num[i+1] )
            {
                if ( ans == -1 )
                {
                    ans = count;
                }
                else
                {
                    ans = gdc ( ans, count );
                }
                count = 1;
            }
            else
            {
                count ++;
            }
        }
        if ( ans == -1 )
        {
            ans = count;
        }
        else
        {
            ans = gdc ( ans, count );
        }

        if ( flag )
        {
            if ( ( ans % 2) )
            {
                printf ( "%d\n", ans );
            }
            else
            {
                for ( ; ! (ans % 2); ans/=2 );
                printf ( "%d\n", ans );
            }

        }
        else
        {
            printf ( "%d\n", ans );
        }
    }
    return 0;
}