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

看别人代码这么短，还以为高精度代码有这么短的哪，原来是没有用高精度啊。我用高精度加DP写了3K多。

Posted by yygy at 2012-11-23 01:19:32 on Problem 1091
In Reply To:__int64 0 毫秒水过 ； Posted by:117474335 at 2010-09-25 17:54:33
> #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:

User ID:
Title:

Content: