NYOJ 102(高次幂取模)

1.二分递归：

使用a*b(mod   n)=(a(mod   n)*b(mod   n))(mod   n)即可。 

#include<stdio.h>
/*
错误
long long fun(long long a,long long b,long long c)
{
	long long temp;
	if(0==b)
		return 1;
	temp=fun(a,b/2,c);
	if(b&1)
		return temp*a%c;
	return temp;
}
*/
/*
AC
long long fun(long long x,long long y,long long p)

{

	long long t=x;

	long long ans=1;

	while(y)

	{

	if(y&1)

	ans=t*ans%p;

	t=t*t%p;

	y=y>>1;
	}
	return (int)ans;
}
*/
long long fun(long long a,long long b,long long c)
{
	long long temp,ans;
	if(0==b)
		return 1;
	temp=fun(a,b/2,c);
	ans=temp*temp%c;
	if(b&1)
		return ans*a%c;
	return ans;
}
/*
TLE
long long fun(long long a,long long b,long long c)
{
	long long temp,ans;
	int i;
	ans=a%c,temp=1;
	for(i=0;i<b;i++)
		temp=(ans*temp)%c;
	return temp;
}
*/
int main()
{
	int i,T;int num;
	long long a,b,c;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		printf("%lld\n",fun(a,b,c));
	}
	return 0;
}

2.s   =   (p   ^   e)   mod   n   =   ((p   mod   n)   ^   e)   mode   n。 

所以，只需要对p除以n的余数进行e次方的运算，而且每运算一步都进行一次取模就可以了。 

做密码的程序需要一点数论基础。