快速幂

//照着幻灯片直接复制上来用来凑字数的随笔

•递归代码

•int f(int a,int b,int n){

•    if(b==1) return a;

•    if(b%2==0){

•        int t=f(a,b/2,n);

•        return t*t%n;

•    }else{

•        int t=f(a,b/2,n);

•        t=t*t%n;

•        t=t*a%n;

•        return t;

•    }

•}

 这个正常人看不懂

•非递归代码

•int f(int a,int b,int n){

•    int ret=1;

•    while(b != 0){

•        if(b%2==1) ret*=a;

•        a=a*a%n;

•        b=b/2;

•    }

•    return ret;

•}

 这个是低配版的·