编程知识 cdmana.com

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<bits/stdc++.h>
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<<s<<endl;
	}
}

版权声明
本文为[mooczhimahu]所创,转载请带上原文链接,感谢
https://blog.csdn.net/mooczhimahu/article/details/126150604

Scroll to Top