Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

__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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator