编程求x^y^最后三位数表示的整数

输入格式:

输入在一行中给出两个整数x和y,其中1<=x,y<=1000000000

输出格式:

输出占一行,是x^y^的最后三位表示的整数。

输入样例1:

在这里给出一组输入。例如：

1
2 3

输出样例1:

在这里给出相应的输出。例如：

1
8

输入样例2:

在这里给出一组输入。例如：

1
12  6

输出样例2:

在这里给出相应的输出。例如：

1
984

思路

快速幂，可使用递归或迭代实现，具体看视频了解（想参加算法竞赛的话）。显示后三位数，意思是结果对1000取余，需要了解取余法则（同样是算法竞赛必备知识）

代码

递归如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;
constexpr long long MOD = 1000;

long long func(long long a, long long b) {
    if(b == 0) {
        return 1;
    }
    long long t = func(a, b / 2);
    return b % 2 == 0 ? t % MOD * t % MOD % MOD : t % MOD * t % MOD * a % MOD;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << func(a % MOD, b) << endl;
    return 0;
}

迭代如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int x, y;
	cin >> x >> y;
	int ans = 1;
	while(y > 0) {
		if(y%2 == 0) {
			y = y/2;
			x = x*x%1000;
		}
		else {
			y--;
			ans = ans*x%1000;
			y /= 2;
			x = x*x%1000;
		}
	}
	cout << ans;
}