POJ 1845 - Sumdiv ( 数论 + 唯一分解定理 + 快速幂取模 )

这是一道数论的好题，需要较好的数学基础

题意: 给定A,B，求A^B的所有因数的和，再MOD 9901

分析：

这里用到了数论当中相当一部分知识

a. 唯一分解定理

任何一个整数都可以分解为若干个素数的幂的乘积的形式

A = ( p1 ^ q1 + p2 ^ q2 + ..... + pn ^ qn ) p为素数

A^B = ( p1 ^ (q1*B) + p2 ^ (q2*B) + ..... + pn ^ (qn*B) )

b. 约数和公式

Sum( A ) = ( 1 + p1 + p1^2 + .... + p1^q1 ) * ( 1 + p2 + p2^2 + .... + p2^q2 ) * ...... * ( 1 + pn + pn^2 +.....+ pn^qn )

Sum( A^B ) = (1 + p1 + p1^2 + .... + p1^(q1*B) ) * ( 1 + p2 + p2^2 + .... + p2^(q2*B) ) * ...... * ( 1 + pn + pn^2 +.....+ pn^(qn*B) )

c. 快速幂取模（略去）

d. 简单的模计算公式 

(a*b)%M = (a%M)*(b%M)%M

e. 递归求解等比数列前n项和 （或者是用乘法逆元来求，还不会，马上补上）

 ( 1 + p1 + p1^2 + .... + p1^n )    分奇偶进行讨论：

1.)　　　　n 为 奇数 ( n & 1 ), 总共有偶数项 ,假设n == 5

 ( 1 + p1 + p1^2 + p1^3 + p1^4 + p1^5  ) = ( 1 + p1 + p1^2 + p1^3 (1 + p1 + p1^2 ) )

=( 1 + p1 + p1^2 + p^(5/2+1) (1 + p1 + p1^2) )

=( 1+ p^(5/2+1) ) * (1 + p1 + p1^2 ) 

转化为一般式应该为

 ( 1 + p1 + p1^2 + .... + p1^n )

= ( 1 + p1 + p1^2 + .... + p1^(n/2) + p^(n/2+1) * (1 + p1 + p1^2 + ..... p1^(n/2)) )

=(1 + p^(n/2+1)) * (1 + p1 + p1^2 + ..... + p1^(n/2))

=(1 + fast_mod(p1,n/2+1) ) * sum(p1,n/2) 

2.)　　　　n 为 偶数 总共有奇数项 ,假设n == 6

 ( 1 + p1 + p1^2 + p1^3 + p1^4  + p1^5 + p1^6 ) = ( 1 + p1 + p1^2 + p1^3 + p1^4 (1 + p1 + p1^2) )

=( 1 + p1 + p2 + p1^4( 1 + p1 + p2 ) + p1^3 )

=( (1 + p^4)( 1 + p1 + p2 ) + p1^3  )

转化为一般式子为

 ( 1 + p1 + p1^2 + .... + p1^n )

 =( 1 + p1^(n/2+1) ) * ( 1 + p1 + p2 + ... + p^(n/2-1) ) + p1^(n/2)

=( 1 + fast_mod(p1,n/2+1) )* sum( p1, n/2-1 )  + fast_mod(p1,n/2)

f.乘法逆元，弱菜太弱，还不会，马上补上

首先我们需要知道等比数列的前N项和 

然后除以(1-q)转化为乘法逆元来做

最后给出代码

/* ***********************************************ID      : whiteblock63LANG    : G++PROG    : POJ - 1845 SumdivDATE    : 2014-10-06 15:56:09************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#define CLR( a, b )        memset( a, b, sizeof(a) )using namespace std;typedef long long LL;typedef unsigned long long ULL;#define MAXN 10000#define MOD 9901LL A, B; //fast_pow_modLL fast_mod( LL a, LL b ){    LL ans = 1;    a = a % MOD;    while( b ){        if( b & 1 )    ans = ans * a % MOD;        a = a * a % MOD;        b >>= 1;    }     return ans;}LL factors[MAXN][2];int fn;//分解质因数void gaoji( LL x ){    fn = 0;    for( LL i = 2; i*i <= x; ++i ){        if( x % i )    continue;        factors[++fn][0] = i;        factors[fn][1] = 0;        while( x % i == 0 ){            factors[fn][1]++;            x /= i;        }    }    if( x != 1 ){        factors[++fn][0] = x;        factors[fn][1] = 1;    }}//递归求解等比数列LL sum( LL p, LL n){    if( n == 0 )    return 1;    if( p == 0 )    return 0;    if( n & 1 )        return ( sum(p, n/2) * (1 + fast_mod( p, n/2 + 1 )) ) % MOD;    else        return ( sum(p, n/2-1) * (1 + fast_mod( p, n/2 + 1 )) + fast_mod( p, n/2 ) ) % MOD;}void Orz(){    scanf( "%lld %lld", &A, &B);    gaoji( A );    LL ans = 1;    for( int i = 1; i <= fn; ++i ){        ans = ans * ( sum( factors[i][0], B*factors[i][1] ) ) % MOD;    }    printf("%lld\n", ans);}int main(){    Orz();    return 0;}

代码君

POJ 1845 - Sumdiv ( 数论 + 唯一分解定理 + 快速幂取模 )