总时间限制: 1000ms 内存限制: 65536kB 描述 已知长度最大为200位的正整数n,请求出2011^n的后四位。 输入 第一行为一个正整数k,代表有k组数据,k<=200接下来的k行, 每行都有一个正整数n,n的位数<=200 输出 每一个n的结果为一个整数占一行,若不足4位,去除高位多余的
时间: 2023-05-26 10:04:31 浏览: 81
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: