首页 > 专题系列 > Java解POJ > POJ 1845 Sumdiv [解题报告] Java
2013
11-10

POJ 1845 Sumdiv [解题报告] Java

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)