sdut 2605 预处理A^N mod p

http://blog.csdn.net/i_am_a_winer/article/details/44905701

http://blog.csdn.net/i_am_a_winer/article/details/44905701

http://blog.csdn.net/i_am_a_winer/article/details/44905701

http://blog.csdn.net/i_am_a_winer/article/details/44905701

http://blog.csdn.net/i_am_a_winer/article/details/44905701

转载的博客思路，学习学习

设：A^N=A^(k*x+y)。即：N=k*x+y，x=N/k，y=N%k。由于N为10^9，所以，k取33333左右就可以了，这样x和y的取值都不超过33333了。

则快速幂变成了：A^N mod P=A^(k*x+y) mod P=(A^(k*x) * A^y )mod P=(A^(k*x) mod P * (A^y) mod P) mod P。由于A，k，P都是定值，则A^N mod P 的值只取决于x和y。分别用dpx和dpy来记录A^(k*x) mod P和A^y mod P，则又可得到：

A^N=(dpx *dpy)mod P。

下面是该如何求dpx和dpy呢？

显然：A^y mod P=A*A^(y-1) mod P=(A mod P *(A^(y-1)) mod P) mod P。即：dpy=(A mod P * dp(y-1)) mod P。

同样的：A^(k*x) mod P=(A^k mod P * A^(k*(x-1)) mod P) mod P。即：dpx=(A^k mod P *dp(x-1)) mod P。

AC,1196ms 下面是这题榨取出来的模板

const int kk=31623;//sqrt(1000000000)
ll dpx[kk];
ll dpy[kk];
void init(ll A,ll p)//预处理ans=A^NmodP   ans=((dpx[N/kk])*(dpy[N%kk]))%p
{
	dpx[0]=dpy[0]=1;
	dpy[1]=A%p;
	for(int i=2; i<=kk; i++)
	{
		dpy[i]=(dpy[1]*dpy[i-1])%p;
	}
	dpx[1]=dpy[kk];
	for(int i=2; i<=kk; i++)
	{
		dpx[i]=(dpx[1]*dpx[i-1])%p;
	}
}