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<iostream>  
#include<cstring>  
#include<algorithm>  
#include<cstdio>  
#include<cmath>  
 
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<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>

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 ;
}