费马小定理+快速幂：ACM-ICPC 2018 焦作赛区网络预赛 G. Give Candies

限制时间是1S，试了试Java的大数运算，超时了。发现虽然 N 的值大的可怕但结果是取余后的，可以通过费马小定理减小指数大小后快速幂得到结果。

快速幂运算时必须加上取余， (a * b) % p = (a % p * b % p) % p ！

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MOD 1000000007
long long FastPowOf2(long long num)
{
	long long sp=1,base=2;
	while(num)
	{
		if(num&1)
			sp=(sp%MOD*base)%MOD;
		base=(base*base)%MOD;
		num>>=1;
	}
	return sp;
}
int main(int agrc,char **argv)
{
	char *BigArray=(char*)malloc(sizeof(int)*100005);
	int cnt;
	scanf("%d",&cnt);
	while(cnt--)
	{
		scanf("%s",BigArray);
		int i;
		long long sum;
		for(i=0,sum=0;i<strlen(BigArray);i++)
			sum=(sum*10+BigArray[i]-'0')%(MOD-1);
		printf("%lld\n",FastPowOf2(sum-1));
	}
	return EXIT_SUCCESS;
} 

END