快速求幂算法的实质是"反复平方法计算幂次式"(倍增法)
模拟一个过程就明白了:
计算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\)也可以用倍增法加速。