#include <stdio.h>
#include <math.h>
#include <stdlib.h>

__int64 n, m, pri[16], k = 0 , ans = 0 ;

__int64 pow1 (__int64 x, __int64 y)
{
    __int64 i, t = 1; 
    for (i = 1; i <= y ; i ++ )
        t *= x ;
    return t ; 
} 

void dfs (__int64 a[], __int64 nu )
{
    __int64 i , t ;
    if (nu > a[0]){
        t = m ;
        for (i = 1; i <= a[0]; i ++ )
            t /= pri[a[i]] ;
        t = pow1 (t, n) ;
        if (a[0] % 2) t = -t ;
        ans += t ;
        return ;}
    if (nu == 1) i = 1 ;
    else i = a[nu - 1] + 1 ;
    for (; i <= k - a[0] + nu ; i ++ ){
        a[nu] = i ;
        dfs (a, nu + 1 ) ;}
}

main ()
{
    __int64 i , j, t , q[20] ;
    scanf ("%I64d%I64d", &n, &m ) ;
    j = m ;
    t = sqrt (m) ;
    for (i = 2 ;i <= t ;i ++ )
        if (m % i == 0 ){
            while (m % i == 0)
                m /= i ;
            pri[ ++ k ] = i ;}
    if (m != 1) pri[ ++ k] = m ;
    m = j ;
    ans = pow1 (m, n) ;
    for (i = 1; i <= k ;i ++ ){
        q[0] = i ;
        dfs (q, 1) ;}
    printf ("%I64d\n", ans) ;
    system ("pause") ;
}

• Re:__int64 0 毫秒水过 ； (1242) lovexinbao 2011-05-11 21:04:09
• Re:__int64 0 毫秒水过 ； (1261) lovexinbao 2011-05-11 21:15:52
• 看别人代码这么短，还以为高精度代码有这么短的哪，原来是没有用高精度啊。我用高精度加DP写了3K多。 (1235) yygy 2012-11-23 01:19:32