Ryan_<

快速求幂算法的实质是"反复平方法计算幂次式"（倍增法）

模拟一个过程就明白了:

计算3^10

3^10   ----a=3,x=10,res=1;

=(3^2)^5   -----a=3^2;x=10/2=5;

=(3^2)^4 * (3^2)^1

=(3^2^2)^2  -----a=(3^2)^2;x=(5-1)/2=floor(5/2)=2;res*=(3^2);

=(3^2^2^2)^1   ------a=(3^2^2)^2;x=(1-1)/2=floor(1/2)=0;res*=(3^2^2^2);

res即为结果.

计算a^N,乘法次数为O(logN).

POJ 1845 Sumdiv

#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 9901
LL A, B; 

//fast_pow_mod
LL 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;
}

研究对象由数转化为矩阵呢？

矩阵乘法最重要的性质就是满足结合律，\((AB)C=A(BC)\)

因此和幂取模一样，\(A^n\)也可以用倍增法加速。