分治的思想

题目如下

赵宗昌老师的课件

---

赵老师真强

分治的基本条件就是能将一个大问题转化为若干具有相同或相似性质的小问题。

这个题就是一个很好的例子

在后半段中提取一个公因子。是的因式分解后某一括号内的多项式和之前的有重叠。这样就可以如此递归下去，直到到了边界条件。

这样，就将O(n)的算法降到O(logn)级别，速度大大增加。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int kasumi(int x,int n,int p)//快速幂
{
	int t=1;
	while(n>0)
	{
		if(n&1)
			t=(t*x)%p;
		n>>=1;
		x=(x*x)%p;
	}
	return t;
}
int work(int x,int n,int p)//递归函数
{
	if(n==1)
		return x%p;
	int s=work(x,n>>1,p)%p;
	if((n&1)==0)
		return (s+kasumi(s,n>>1,p)*s)%p;
	else
		return ((s+kasumi(s,n>>1,p)*s)%p+kasumi(s,n,p))%p;
}
int main()
{
	int x,n,p;
	scanf("%d%d%d",&x,&n,&p);
	printf("%d",work(x,n,p));
	return 0;
}