數(shù)學(xué)題，證明可以看DISCUSS.
#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 ( int 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 main ()
{
    
    int t;
    int n;
    int i, j;
    
    int len = find ( MAX );
    while ( scanf ( "%d", &t ) != EOF )
    {
        for ( j=1; j<=t; j++ )
        {
            int in;
            scanf ( "%d%d", &in, &n );
            pre = 0;
            while ( n != 1 )
            {
                n = f ( n, len );
            }
            for ( i=0; i<pre; i++ )
            {
                if ( num[i] != 2 )
                {
                    break;
                }
            }
            printf ( "%d ", j );
            if ( i >= pre )
            {
                printf ( "0\n" );
            }
            else
            {
                int ans = 1;
                int count = 1;
                for ( i++ ; i<pre; i++ )
                {
                    if ( num[i] != num[i-1] )
                    {
                        ans *= ( count + 1 );
                        count = 1;
                    }
                    else
                    {
                        count ++;
                    }
                }
                ans *= ( count + 1 );
                
                printf ( "%d\n", ans-1 );
            }
        }
    }
    return 0;
}