> #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") ;
> }
厉害 果然妙过