(POJ) Pseudoprime numbers [快速冪]

http://poj.org/problem?id=3641

裡面有快速冪的code :

#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <math.h>
using namespace std;
int main () {
    long long int p,a;
    while (scanf("%lld %lld",&p,&a) != EOF) {
        //check p!=prime first
        if (!p&&!a) return 0;
        long long int t=sqrt(double(p));
        bool prime=true;
        for (int x=2;t>=x;x++) {
            if (p%x==0) {
                prime=false;
                break;
            }
        }
        if (prime && t*t!=p ) {
            puts("no");
            continue;
        }
        //快速密
//        puts("hi");
        long long int _2n[40];
        _2n[0]=a;
        _2n[0]%=p;
        for (int x=1;40>x;x++) {
            _2n[x]=_2n[x-1]*_2n[x-1];
            _2n[x]%=p;
        }
        long long tmp=1;
        long long tmpa=p;
        int id=0;
        long long check=1;
        while (tmpa>0) {
            long long tmpb=tmpa>>1;
            if (tmpb*2==tmpa) id++;
            else {
                check*=_2n[id];
                id++;
                check%=p;
            }
            tmpa=tmpb;
        }
        if (check%p==a%p) puts("yes");
        else puts("no");
    }
}