好久没写博客了，今天来水一波。犹记得大一寒假时，我在洛谷刷题，见到了一种奇怪的题型，由于用到了很多的幂运算，最后的答案很大，要求输出其最后三位数字，我提交之后，爆了WA以及TLE，当时查看题解以及百度，说要使用快速幂取模处理，当时看了半天（真的有半天），看得一知半解，最后也没有搞懂。最近算法水平有所提升，再看快速幂，十分钟就搞懂了，当时真的太呆了。。。

　　那么，何为快速幂（FFT）呢？在我看来，这是一种利用二进制来加速幂运算的绝妙的基础算法。拿a^15举例，因为11=1+2+4+8=2^0+2^1+2^2+2^3，我们可以将它分解为a^11=a^1 * a^2 * a^4 * a^8，,而15的二进制为1111，可以看出，原本要进行15次的运算，现在只要3次即可。对于任意整数n而言，我们可以将时间复杂度从O(n)降低到O(logn)。并且，为了避免WA，在每次相乘时，都进行取模操作即可。因为(a+b)%m==(a%m+b%m)%m,  (a-b)%m==(a%m-b%m)%m,   (a*b)%m==(a%m*b%m)%m，然而这个规律对于除法不适用，应注意。

　　例题1 hdu2817

A sequence of numbers

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11160    Accepted Submission(s): 3342

Problem Description Xinlv wrote some sequences on the paper a long time ago, they might be arithmetic or geometric sequences. The numbers are not very clear now, and only the first three numbers of each sequence are recognizable. Xinlv wants to know some numbers in these sequences, and he needs your help. Input The first line contains an integer N, indicting that there are N sequences. Each of the following N lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is K, indicating that we want to know the K-th numbers of the sequence.
You can assume 0 < K <= 10^9, and the other three numbers are in the range [0, 2^63). All the numbers of the sequences are integers. And the sequences are non-decreasing. Output Output one line for each test case, that is, the K-th number module (%) 200907. Sample Input 2 1 2 3 5 1 2 4 5 Sample Output 5 16   经典快速幂例题，注意开long long以及取模即可 代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int modd=200907;
int main(){
    ll n;
    while(~scanf("%lld",&n)){
        while(n--){
            ll a,b,c,p;
            scanf("%lld%lld%lld%lld",&a,&b,&c,&p);
            ll ans;
            if(b-a==c-b){
                ans=a+(b-a)*(p-1);
            }
            else{
                ans=a;
                ll base=b/a;
                ll m=p-1;
                while(m){
                    if(m&1)ans=(ans*base)%modd;
                    base=(base*base)%modd;
                    m>>=1;
                }
            }
            printf("%lld\n",ans%modd);
        }
    }
    return 0;
}

例题2 hdu1061

Rightmost Digit

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 95341    Accepted Submission(s): 35027

Problem Description Given a positive integer N, you should output the most right digit of N^N. Input The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000). Output For each test case, you should output the rightmost digit of N^N. Sample Input 2 3 4 Sample Output 7 6   就是要求n^n的末位数字利用快速幂取模即可。 代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    cin>>t;
    while(t--){
        ll n;
        ll ans=1;
        scanf("%lld",&n);
        ll base=n;
        while(n){
            if(n&1)ans=(ans*base)%10;
            base=(base*base)%10;
            n>>=1;
        }
        printf("%lld\n",ans%10);
    }
    return 0;
}