Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## __int64 0 毫秒水过 ；

Posted by 117474335 at 2010-09-25 17:54:33 on Problem 1091
```#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") ;
}
```

Followed by: