B2075

· · 题解

题目

B2075

思路

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

方法一

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

方法二

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

\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}