标题 整数分析 类别 流程控制 时间限制 1s 内存限制 256kb 问题描述 给出一个整数n（0<=n<=100000000）。求出该整数的位数，以及组成该整数的所有数字中的最大数字和最小数字。 输入说明 输入一个整数n（0<=n<=100000000） 输出说明 在一行上依次输出整数n的位数，以及组成该整数的所有数字中的最大数字和最小数字，各个数字之间用空格分隔。 输入样例 217 输出样例 3 7 1

题目描述：给出一个整数n（1<=n<=100000000），求该整数的位数，以及组成该整数的所有数字中的最大和最小数字。要求程序运行时间不超过1秒，内存限制为256kb。

解题思路：题目要求计算一个很大的整数的位数和最大/最小数字，而该整数可以有10^8位，超出了int等类型的表示范围。因此我们可以将该整数转化为字符数组，然后对其进行各种计算。

具体来说，我们可以先求出该整数的位数，这可以通过字符串的长度计算得到。然后我们可以使用桶排序的思想，对该整数中的所有数字进行计数，并记录最大和最小数字，最后输出即可。

时间复杂度：O(n)，其中n为该整数的位数。由于n<=10^8，因此需要使用O(1)的空间存储字符数组。

代码如下：

相关问题

总时间限制: 1000ms 内存限制: 65536kB 描述 已知长度最大为200位的正整数n，请求出2011^n的后四位。 输入 第一行为一个正整数k，代表有k组数据，k<=200接下来的k行， 每行都有一个正整数n，n的位数<=200 输出 每一个n的结果为一个整数占一行，若不足4位，去除高位多余的

0，不足4位则用前导0补足4位。

样例输入

2
3
123456789876543211234567898765432112345678987654321
样例输出

8083
5201

解题思路：

快速幂

这道题普及的做法不必使用 c++ 取模坑函数。

求幂 的几个算法

最基础的算法，直接循环 $n$ 次，复杂度为 $\Theta(n)$

int pow(int a,int n) {
int ans=1;
for(int i=1;i<=n;i++) ans*=a;
return ans;
}

快速幂，复杂度 $\Theta(\log_2 n)$

将 $n$ 分解为二进制位展开的和：

$n = a_0 * 2^0 + a_1 * 2^1 + \cdots + a_m*2^m$

- $a_i$ 取 $0$ 或 $1$

a_i = n&1;
n>>=1;

然后采用如下方式，计算出 $a^n$ :$

^ 调用函数表示幂运算
\begin{aligned}a^n = [ \begin{cases}1&(n=0)\cr a^{n/2}\times a^{n/2} & (n \% 2 = 0)\cr a^{n/2}\times a^{n/2} \times a & (n \% 2 = 1)\cr \end{cases} \end{aligned}

用递归的方式，无论对于何种情况，都可以尽可能的快的计算出幂值

int pow(int a,int n){
if(n==0) return 1;
int ans=pow(a,n>>1);
ans=ans*ans;
if(n&1) ans*=a;
return ans;
}

当然，还有迭代的做法，不过见下文的题解即可。

解题思路

此题是一道判断你对快速幂算法的掌握且计算值比较大的简单水题。

题面给出一个 $n$ ，要剖析出 $2011 ^ n$ 的最后四位。

直接计算是不可能的，只能使用快速幂的算法，

和最简单的快速幂的三步算法有些不同，

首先我们有一个数 $ans=1$

每一次计算 $n$ 二进制码的最低位，

如果是 $1$ ，就要将 $ans$ 乘以 $2011^n$ ，否则 $n=n/2$ 即可。

int power(int n){
int ans=1,sum=2011;
while(n){
if(n&1) ans=(ans*sum)%10000;//最后保留四位
sum=sum*sum%10000;
n>>=1;
}
return ans;
}

性能测试:$8 cases$

方法 max_cpu_time max_real_time max_memory

递归 $1s$ $1s$ $128MB$
循环 $1s$ $1s$ $128MB$
快速幂(iterative) $1000ms$ $1000ms$ $128MB$

注意，在计算过程中每一步都要对答案取模，不然答案可能会爆掉。

code:

标题 累加和校验 类别 流程控制 时间限制 1s 内存限制 256kb 问题描述 数据传输中一种常见的校验方式是累加和校验。其实现方式是在一次通讯数据包的最后加入一个字节的校验数据。 这个校验字节内容为前面数据包中所有数据按字节累加所得结果的最后一个字节。例如： 要传输的信息为： test（ascii码为0x54,0x45,0x53,0x54） 四个字节的累加和为：0x54+0x45+0x53+0x54=0x140 校验和为累加和的最后一个字节，即0x40，也就是十进制的64 现在请设计一个程序计算给出的待传输信息的累加校验和 输入说明 输入为一个字符串，字符串长度不超过100个字符 输出说明 输出一个十进制整数，表示输入字符串的累加校验和。 输入样例 test 输出样例 64

本题是关于累加和和校验的流程控制问题。时间限制为1秒，内存限制为256kb。问题描述数据传输中一种常见的校验方式是累加和和校验。其实现方式是在一次通讯数据包的最后加入一个字节的校验码，校验码为前面所有数据的按字节相加的和取反加1。例如：要传输的信息为：test（ascii码为0x54,0x45,0x53,0x54），四个字节的累加和为0x54+0x45+0x53+0x54=0x140，校验和为累加和的最后一个字节，即0x40，也就是十进制的64。 现在请设计一个程序计算出待传输信息的累加和校验和。 输入说明输入为一个字符串，字符串长度不超过100个字符。 输出说明输出一个十进制数字，表示输入字符串的累加和校验和。 输入样例test 输出样例64