2013
11-10

# Sumdiv

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).

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

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

2 3

15

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).

import java.util.*;
public class Main {

static long modPow(long a,long n)
{
long MOD=9901;
if (n==1) return a%MOD;
long tmp=modPow(a,n>>1);
tmp=tmp*tmp%MOD;
if ((n&1)==1) tmp=tmp*a%MOD;
return tmp;
}

static long myPow(long a,long n)
{
if (n==0) return 1;
long ans=modPow(a,(n>>1)+1);
ans=(ans+1)%9901;
if ((n&1)==1)
ans=ans*myPow(a,n>>1)%9901;
else
{
ans=ans*myPow(a,(n-1)>>1)%9901;
ans=ans+modPow(a,n>>1);
}
return ans%9901;
}

public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
long a=cin.nextLong();
long b=cin.nextLong();
long ans=1;
for (long i=2;i*i<=a;i++)
if (a%i==0)
{
long pow=0;
while (a%i==0)
{
a/=i;
pow++;
}
pow*=b;
ans=ans*myPow(i,pow)%9901;
}
if (a!=1)
ans=ans*myPow(a,b)%9901;
System.out.println((ans+9901)%9901);
}
}

1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)