Time Limit: 1000MS  Memory Limit: 30000K

Total Submissions: 4943  Accepted: 1047

Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

 

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

 

Output

The only line of the output will contain S modulo 9901.

 

Sample Input

2 3

 

Sample Output

15

Hint

2^3 = 8.

The natural divisors of 8 are: 1,2,4,8. Their sum is 15.

15 modulo 9901 is 15 (that should be output).

 

Source

Romania OI 2002

---

//

 POJ1845.cpp : Defines the entry point for the console application.

#include 

<

iostream

>

using

 

namespace

 std;

#define

 M 9901

#define

 MAX 10000

long

 

long

 pow(

long

 

long

 x,

long

 

long

 n)

{

    

long

 

long

 ret

=

1

,s

=

x;

    

while

 (

true

)

    {

        

if

 (n 

&

 

1

) ret 

=

 ((ret 

%

 M) 

*

 (s 

%

 M)) 

%

 M;

        

if

 (n

>>=

1

) s 

=

 ((s 

%

 M) 

*

 (s 

%

 M)) 

%

 M;

        

else

 

break

;

    }

    

return

 ret;

}

long

 

long

 sum(

long

 

long

 p,

long

 

long

 n)

{

    

if

(n 

==

 

0

)

        

return

 

1

;

    

if

(n 

&

 

1

)

        

return

 (((

1

+

pow(p,n

/

2

+

1

)) 

%

 M) 

*

 (sum(p,n

/

2

) 

%

 M)) 

%

 M;

    

else

        

return

 (((

1

+

pow(p,n

/

2

+

1

)) 

%

 M) 

*

 (sum(p,(n

-

1

)

/

2

) 

%

 M) 

+

 pow(p,n

/

2

) 

%

 M) 

%

 M;

}

int

 main(

int

 argc, 

char

*

 argv[])

{

    

int

 A,B;

    

int

 p[MAX],c[MAX];

    memset(p, 

0

, 

sizeof

(p));

    memset(c, 

0

, 

sizeof

(c));

    cin

>>

A

>>

B;

    

for

(

int

 i 

=

 

2

;i 

*

 i 

<=

 A;

++

i)

    {

        

if

(A 

%

 i 

==

 

0

)

        {

            p[

++

p[

0

]] 

=

 i;

            

while

(A 

%

 i 

==

 

0

)

            {    

                A 

/=

 i;

                

++

c[p[

0

]];

            }

        }

    }

    

if

(A 

!=

 

1

)

    {

        p[

++

p[

0

]] 

=

 A;

        c[p[

0

]] 

=

 

1

;

    }

    

long

 

long

 res

=

1

;

    

for

(

int

 i 

=

 

1

;i 

<=

 p[

0

]; 

++

i)

    {

        res 

=

 ((res 

%

 M) 

*

 (sum(p[i],B 

*

 c[i]) 

%

 M)) 

%

 M;

    }

    cout

<<

res

<<

endl;

    

return

 

0

;

}