poj1845-Sumdiv

这道题目的题意为求Ａ　^ B 的值的所有的因子的和。因此需要用到快速幂，可以知道需要求解的就是求　１＋A ^ 1 + A ^ 2 + A ^ 3 + .........+ A ^ B。但是直接求解的话，存在几种问题，一是会ＭＬＥ，还有就是会ＴＬＥ。因为，Ａ无法保证全部为最简值，就是仍然可以分解，因此，需要将Ａ也拆分为多组；然后将每组的幂次求解出来再相乘，仍然可以得出题解，就是 Ａ ＝ p1 * p2 * p3 * ............ * pn;然后题目就转换成求( １　＋　p1 ^ 1 + p1 ^2 。。。。。。＋　p1 ^ b1 )* (........)，直接使用等比数列求和，也容易MLE，因此，等比数列求和还可以由如下解法(二分）：

假设p为公比，n为最大幂次数；

A、当 n 为奇数时 ，（ 1 + p ^ ( n / 2 + 1 ) ） * ( 1 + p ^ 1 + ........ + p ^ ( n / 2 ) ) ;

B、当 n 为偶数时 ，（ 1 + p ^ ( n / 2 + 1 ) ) * ( 1 + p ^ 1 + ......... + p ^ ( ( n - 1 ) / 2 ) ) + p ^ ( n / 2 ) ;

这里可以使用递归来求解

#include  
#include  
#include  
#include  
#include  
 
using namespace std; 
#define MOD 9901  
#define INT __int64  
#define MAX 10000   
int A , B ; 
int count1 ; 
int p[ MAX ] , c[ MAX ] ; 
 
int Pow( INT x , INT n )   
{   
    INT temp = x ;   
    INT ans = 1 ;   
    while( n )   
    {   
        if( n % 2 == 1 )   
        {   
            n-- ;   
            ans = ( ( ans % MOD ) * ( temp % MOD ) ) % MOD ;   
        }   
        else   
        {   
            n /= 2 ;   
            temp = ( (temp % MOD ) * ( temp % MOD ) ) % MOD ;   
        }   
    }   
    return ans ;   
}    
 
INT sum( INT p , INT n ) 
{ 
    if( n == 0 ) 
        return 1 ; 
    if( n & 1 ) 
        return ( ( ( 1 + Pow( p , n / 2 + 1 ) ) % MOD * ( sum( p , n / 2 ) % MOD ) ) % MOD ) ; 
    else 
        return ( ( ( 1 + Pow( p , n / 2 + 1 ) ) % MOD * ( sum( p , ( n - 1 ) / 2 ) % MOD ) )+ Pow( p , n / 2 ) % MOD ) ; 
}  
int main() 
{ 
    cin >> A >> B ; 
    for( int i = 2 ; i * i <= A ; ++i ) 
    { 
        if( A % i == 0 ) 
            p[ ++count1 ] = i ; 
        while( A % i == 0 ) 
        { 
            A /= i ; 
            c[ count1 ] ++ ; 
        } 
    } 
     
    if( A != 1 ) 
    { 
        p[ ++count1 ] =  A ; 
        c[ count1 ] = 1 ; 
    }  
    INT ans = 1 ; 
    for( int i = 0 ; i <= count1 ; ++i ) 
        ans = ( ( ans % MOD ) * ( sum( p[ i ] , B * c[ i ] ) ) % MOD ) % MOD ; 
    cout << ans << endl ;  
} 

#include
#include
#include
#include
#include

using namespace std;
#define MOD 9901
#define INT __int64
#define MAX 10000
int A , B ;
int count1 ;
int p[ MAX ] , c[ MAX ] ;

int Pow( INT x , INT n ) 
{ 
    INT temp = x ; 
    INT ans = 1 ; 
    while( n ) 
    { 
        if( n % 2 == 1 ) 
        { 
            n-- ; 
            ans = ( ( ans % MOD ) * ( temp % MOD ) ) % MOD ; 
        } 
        else 
        { 
            n /= 2 ; 
            temp = ( (temp % MOD ) * ( temp % MOD ) ) % MOD ; 
        } 
    } 
    return ans ; 
}  

INT sum( INT p , INT n )
{
 if( n == 0 )
  return 1 ;
 if( n & 1 )
  return ( ( ( 1 + Pow( p , n / 2 + 1 ) ) % MOD * ( sum( p , n / 2 ) % MOD ) ) % MOD ) ;
 else
  return ( ( ( 1 + Pow( p , n / 2 + 1 ) ) % MOD * ( sum( p , ( n - 1 ) / 2 ) % MOD ) )+ Pow( p , n / 2 ) % MOD ) ;
}
int main()
{
 cin >> A >> B ;
 for( int i = 2 ; i * i <= A ; ++i )
 {
  if( A % i == 0 )
   p[ ++count1 ] = i ;
  while( A % i == 0 )
  {
   A /= i ;
   c[ count1 ] ++ ;
  }
 }
 
 if( A != 1 )
 {
  p[ ++count1 ] =  A ;
  c[ count1 ] = 1 ;
 }
 INT ans = 1 ;
 for( int i = 0 ; i <= count1 ; ++i )
  ans = ( ( ans % MOD ) * ( sum( p[ i ] , B * c[ i ] ) ) % MOD ) % MOD ;
 cout << ans << endl ;
}