NOI2.4 2011

描述
已知长度最大为200位的正整数n，请求出2011^n的后四位。
输入
第一行为一个正整数k，代表有k组数据，k<=200接下来的k行，

每行都有一个正整数n，n的位数<=200
输出
每一个n的结果为一个整数占一行，若不足4位，去除高位多余的0
样例输入

样例输出

不就是循环n次，输出吗？好水的一道题，哈哈哈！！！

What a water problem it is !!!

不错，这就是不懂事的一种想法，看看n的大小，你会打消这种念头的…………

想起小学时老师就讲过，一个n位数的k次方的后n位数，是可以与n相等的，而现在的n就是2011，我们只需找出它是几次一循环

先写一个小程序，找一下k的值

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

int main()

{

	int i,k=2011;

	for(i=2;;i++)

	{

		k=k*2011%10000;

		if(k==2011)

		{

			printf("%d",i-1);

			return 0;

		}

	}

}

很简单，不必解释了

求出了k的值，500

接下来每个数取后三位就OK了，因为500能整除1000

代码如下：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

int a[1001];

void chu()

{

	int k=1,i;

	for(i=1;i<=1000;i++)

		a[i]=k=k*2011%10000;

}

int main()

{

	chu();

	int n,k,l,i;

	char c[201];

	scanf("%d",&n);

	for(i=1;i<=n;i++)

	{

		scanf("%s",c);

		l=strlen(c);

		if(l==1)k=c[0]-48;

		else if(l==2)k=(c[0]-48)*10+c[1]-48;

		else k=(c[l-1]-48)+(c[l-2]-48)*10+(c[l-3]-48)*100;

		printf("%d\n",a[k]);

	}

}

所以，有时一道题不一定只用一个程序来解决，可以写小程序辅助一下，这就是分治

巴特西

NOI2.4 2011

最新文章

热门文章