NOI / 2.4基本算法之分治-2991:2011

如果您没有dev-c++，可使用线上编辑器：GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C++。

题目 

连接：OpenJudge - 2991:2011

总时间限制: 1000ms内存限制: 65536kB

描述

已知长度最大为200位的正整数n，请求出2011^n的后四位。

输入

第一行为一个正整数k，代表有k组数据，k<=200接下来的k行，

每行都有一个正整数n，n的位数<=200

输出

每一个n的结果为一个整数占一行，若不足4位，去除高位多余的0

样例输入

3
5
28
792

样例输出

1051
81
5521

首先要解决3个问题

一、a有200位，往哪里存？int只能存十位数，long也只能存十九位、但如果用字符串来接，就会轻松很多。

二、计算时会爆int，所以要边乘边%10000。

三、把a存入后怎么用？很显然，我们要用取字符串的方法取出后三位，因为2011的乘方每500个一周期。

完整程序+注释

 #include
using namespace std;
int main()
{
	char a[2000];//200位数只能用字符串接
	int n,i,k,s,len;//s为累乘变量、i用来循环
	cin>>k;//输入组数
	while(k--)//循环k次
	{
		cin>>a;
		len=strlen(a);//判断字符长度
		s=1;//s：2011^n的结果 
		if(len==1)//取后三位数
		n=a[0]-'0';
		if(len==2)
		n=(a[0]-'0')*10+a[1]-'0';
		if(len>=3)
		n=(a[len-3]-'0')*100+(a[len-2]-'0')*10+a[len-1]-'0';
		for(i=1;i<=n;i++)
		s=(s*2011)%10000;//保留后四位数 
		cout<
	}
}