自动搬运

查看原文

来自洛谷，原作者为

	ssss41 俱往矣

搬运于2025-08-24 21:03:14，当前版本为作者最后更新于2021-07-17 09:05:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

B2075

思路

这题暴力肯定不予考虑（一本坑能这么单纯？），那么让我们换一种思路。

方法一

因为它只想要最后三位，所以我们可以用 for 循环模拟幂运算，并且每一次循环都取余1000，这样可以得到它的后三位，并且在最后输出时补齐（在这里借鉴了题解区dalao）。

方法二

难道你们看到幂的时候没有一点想法吗？没错，就是快速幂。由于位运算我不会，所以并没有用那个。快速幂大概是这样的一个递归函数：

$ qp(a,b)=\left\{ \begin{aligned} & b=0\ &1 \\ & b=1\ &a\\ & b\bmod2=0\ & qp(a,\left\lfloor\frac{b}{2}\right\rfloor)^2\\ & b\bmod2=1\ &qp(a,\left\lfloor\frac{b}{2}\right\rfloor)^2×a \end{aligned} \right. $

这样来看，就没有什么难理解的了，并且之后它的细节和方法一基本相同。

ps.大家如果想练习快速幂可以戳这里。

代码

//方法一
#include <iostream>
#include <cstdio>
using namespace std;
  
long long a, b, s = 1;
 
int main()
{
    cin >> a >> b;
    for(int i = 0;i < b;++i)
        s *= a, s %= 1000; //每乘一次模一次1000
    printf("%03lld", s); //补满3位的0
    return 0;
}

//方法二
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

long long qp (long long a,long long b){//快速幂
    if (b == 0) return 1;
    if (b == 1) return a;
    long long r = 0;
    r = qp(a,b/2) % 1000;
    r = r * r % 1000;
    if (b % 2) r = r * a % 1000;
    return r;
}

long long a,b;

int main(){
    cin >> a >> b;
    long long p = qp (a,b) % 1000;
    printf ("%03lld\n",p);
    system ("pause");
    return 0;
}

求过。

$\texttt{END}$