快速幂&hdu1061

1.快速幂实现a^N

2.RSA
3.hdu1061
4.矩阵快速幂

---

1.快速幂实现a^N

求3^999(a=3,N=999):3 ^ 999 = 3 * 3 * 3 * … * 3，直接乘要做998次乘法。

快速幂方法实质使用了二分法进行时间优化:

 tmp+   =   tmp- *   a-;

3 ^ 1 =    3 *   1

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

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

…………

3 ^ 256 = (3 ^ 128) * (3 ^ 128)

3 ^ 512 = (3 ^ 256) * (3 ^ 256)

==>

3 ^ 999 

= (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3 

只做16次乘法。

将999转为2进制数：1111100111

1    1   1   1  1 0 0 1 1 1

512 256 128 64 32 0 0 4 2 1

各个位上的值即为需要进行乘积的标志。

[CODE]

void my_pow(int a, int b){

    long long unsigned result = 1;

    long long unsigned tmp = 1;

    while(b){

        tmp *= a;

        if(b&1)

            result *= tmp;

        b >>= 1;

        a = tmp;

    }

    printf("%lld\n",result);

}

参考：

%B9%D5%BD%C7%BF%A7%B7%C8%B9%DD/blog/item/c4771ad6ba0b1f15a18bb757.html

---

RSA

RSA加密算法(WIKI)

---

HDU 1061
#include

void my_pow(int a, int b){
    long long unsigned result = 1;
    long long unsigned tmp = 1;

    while(b){
        tmp = tmp * a;
        tmp %= 10;
        if( b&1 ){
            result *= tmp;
            result %= 10;
        }
        b>>=1;
        a = tmp;
    }
    printf("%d\n",result%10);
}

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int a;
        scanf("%d",&a);
        if(a%4){
            my_pow(a,a%4);
        }else{
            my_pow(a,4);
        }
    }

    return 0;
}

---

矩阵快速幂
http://www.cppblog.com/acronix/archive/2010/08/23/124470.aspx?opt=admin