A - A+B for Input-Output Practice (I)

题目

Your task is to Calculate a + b.
Too easy?! Of course! I specially designed the problem for acm beginners.
You must have found that some problems have the same titles with this one, yes, all these problems were designed for the same aim.

你的任务是计算a + b。
太容易了？！当然！这个问题是我专门为ACM初学者设计的。
你一定发现了一些问题与这个问题有着相同的标题，没错，所有这些问题都是为了一个目的设计的。

输入

The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.

输入由多组整数a和b组成，用空格隔开，每行一对整数。

输出

For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.

对于每一对输入整数a和b，你应该在一行中输出a和b的和，每一行的输入都有一行输出。

示例

输入	输出
1 5	6
10 20	30

示例代码

#include <iostream>

// a+b基础加法计算
int sum(int a, int b) {
    return a + b;
}

// 主函数
int main(int argc, const char* argv[]) {
	int a, b; // 定义输入缓存a和b，存储加法运算的左值和右值
    while(std::cin >> a >> b) // 多组数据输入，采用while循环读入
        std::cout << sum(a,b) << std::endl; // 每读入一组数据就经加法函数计算后直接输出结果
    return 0;
}

示例复杂度

时间复杂度为 O(n)

空间复杂度为 O(1)

题意分析

题目很明显的要求是计算a+b的和，示例中也可以看出是这样。同时，根据输入提示，需要一次性处理多组测试用例，所以得做循环输入。因为变量个数恒定，而且数量较少，可采用直接定义变量方式存储，无需使用数组。输出格式要求是一个结果一个换行。

解题思路

根据题意输入a和b的值，将二者相加输出即可。注意多组输入的循环和换行要求。

B - A+B for Input-Output Practice (II)

题目

Your task is to Calculate a + b.

你的任务是计算a+b

输入

Input contains an integer N in the first line, and then N lines follow. Each line consists of a pair of integers a and b, separated by a space, one pair of integers per line.

第一行输入包含一个整数N，然后是N行。每行有一对整数a和b，用空格隔开，每行有一对整数。

输出

For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.

对于每一对输入整数a和b，你应该在一行中输出a和b的和，每一行的输入都有一行输出。

示例

输入	输出
2	6
1 5	30
10 20

示例代码

#include <iostream>

// a+b函数，与A题相同
int sum(int a, int b) {
    return a + b;
}

int main(int argc, const char* argv[]) {
    int n, a, b;
    std::cin >> n; // 与A题的差别就在于指定样例个数
    for(int i = 0; i < n; i++) {
        std::cin >> a >> b;
        std::cout << sum(a,b) << std::endl;
    }
    return 0;
}

示例复杂度

时间复杂度：O(N)

空间复杂度：O(1)

题意分析

与A题相同，就是普通的A+B计算

解题思路

将A题的代码改成指定样例个数的形式输入即可

C - A+B for Input-Output Practice (III)

题目

Your task is to Calculate a + b.

你的任务是计算a+b

输入

Input contains multiple test cases. Each test case contains a pair of integers a and b, one pair of integers per line. A test case containing 0 0 terminates the input and this test case is not to be processed.

输入包含多个测试用例。每个测试用例包含一对整数a和b，每行有一对整数。包含0 0的测试用例终止输入，这个测试用例将不被处理。

输出

For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.

对于每一对输入整数a和b，你应该在一行中输出a和b的和，每一行的输入都有一行输出。

示例

输入	输出
1 5	6
10 20	30
0 0

示例代码

#include <iostream>

// a+b函数，与A题相同
int sum(int a, int b) {
    return a + b;
}

int main(int argc, const char* argv[]) {
    int a, b;
    while(std::cin >> a >> b) {
        if (a == 0 && b == 0) break; // 与A题的不同之处在于左值和右值均为零即结束。
        std::cout << sum(a,b) << std::endl;
    }
    return 0;
}

示例复杂度

时间复杂度：O(N)

空间复杂度：O(1)

题意分析

与A题相同，计算A+B，不过要考虑左值和右值均为0的情况

解题思路

将A题改成左值和右值均为0时break即可。

D - A+B for Input-Output Practice (IV)

题目

Your task is to Calculate the sum of some integers.

你的任务是计算一些整数的和。

输入

Input contains multiple test cases. Each test case contains a integer N, and then N integers follow in the same line. A test case starting with 0 terminates the input and this test case is not to be processed.

输入包含多个测试用例。每个测试用例包含一个整数N，然后在同一行中有N个整数。以0开头的测试用例终止输入，并且这个测试用例不会被处理。

输出

For each group of input integers you should output their sum in one line, and with one line of output for each line in input.

对于每一组输入的整数，你应该在一行中输出它们的和，每一行的输入都有一行输出。

示例

输入	输出
4 1 2 3 4	10
5 1 2 3 4 5	15
0

示例代码

#include <iostream>

// 数组求和函数，输入数组本身和数组大小
int sum(int a[],int size) {
    for (int i = 1; i < size; i++) // 循环求和
        a[0] += a[i];
    return a[0];
}

int main(int argc, const char* argv[]) {
    int n,a[20];
    while (std::cin >> n) { // 多组样例输入
        if (n > 0) {
            for (int i = 0; i < n; i++) // 将输入内容输入数组内部
                std::cin >> a[i];
            std::cout << sum(a,n) << std::endl;
        }
        else break;
    }
    return 0;
}

示例复杂度

时间复杂度：O(n2)

空间复杂度：O(1)

题意分析

这个是数组求和，将数组内的所有整数相加。与A题的不同之处在于求和的数字不限定为2个。

解题思路

将所有数字输入到数组内部，然后循环将数组求和，可以采用a[0]存储其他位的求和内容

E - A+B for Input-Output Practice (V)

题目

Your task is to calculate the sum of some integers.

你的任务是计算一些整数的和。

输入

Input contains an integer N in the first line, and then N lines follow. Each line starts with a integer M, and then M integers follow in the same line.

第一行输入包含一个整数N，然后是N行。每一行都以一个整数M开头，然后同一行有M个整数。

输出

For each group of input integers you should output their sum in one line, and with one line of output for each line in input.

对于每一组输入的整数，你应该在一行中输出它们的和，每一行的输入都有一行输出。

示例

输入	输出
2	10
4 1 2 3 4	15
5 1 2 3 4 5

示例代码

#include <iostream>

// 与D题相同的数组求和函数
int sum(int a[],int size) {
    for (int i = 1; i < size; i++)
        a[0] += a[i];
    return a[0];
}

int main(int argc, const char* argv[]) {
    int tasks;
    std::cin >> tasks;
    for (int i = 0; i < tasks; i++) {
        int n, a[20];
        std::cin >> n;
        for (int j = 0; j < n; j++)
            std::cin >> a[j];
        std::cout << sum(a,n) << std::endl;
    }
    return 0;
}

示例复杂度

时间复杂度：O(n2)

空间复杂度：O(1)

题意分析

与D题类似，也是修改了示例输入方式

解题思路

将D题的代码修改成本题对应输入方式即可

F - A+B for Input-Output Practice (VI)

题目

Your task is to calculate the sum of some integers.

你的任务是计算一些整数的和。

输入

Input contains multiple test cases, and one case one line. Each case starts with an integer N, and then N integers follow in the same line.

输入包含多个测试用例，一个用例一行。每一种情况都从一个整数N开始，然后N个整数在同一行中。

输出

For each test case you should output the sum of N integers in one line, and with one line of output for each line in input.

对于每个测试用例，你应该在一行中输出N个整数的和，并且每一行输入都有一行输出。

示例

输入	输出
4 1 2 3 4	10
5 1 2 3 4 5	15

示例代码

#include <iostream>

// 与D题相同的数组求和函数
int sum(int a[],int size) {
    for (int i = 1; i < size; i++)
        a[0] += a[i];
    return a[0];
}

int main(int argc, const char* argv[]) {
    int n,a[20];
    while (std::cin >> n) { // 不限制样例个数输入
        if (n > 0) {
            for (int i = 0; i < n; i++)
                std::cin >> a[i];
            std::cout << sum(a,n) << std::endl;
        }
        else break;
    }
    return 0;
}

示例复杂度

时间复杂度：O(n2)

空间复杂度：O(1)

题意分析

与D题基本一致

解题思路

与D题基本一致

G - A+B for Input-Output Practice (VII)

题目

Your task is to Calculate a + b.

你的任务是计算a + b。

输入

The input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.

输入由一系列整数a和b组成，用空格隔开，每行一对整数。

输出

For each pair of input integers a and b you should output the sum of a and b, and followed by a blank line.

对于每一对输入的整数a和b，你应该输出a和b的和，然后是空行。

示例

输入	输出
1 5	6
10 20
	30

示例代码

#include <iostream>

// 与A题相同的A+B处理函数
int sum(int a, int b) {
    return a + b;
}

int main(int argc, const char* argv[]) {
    int a, b;
    while (std::cin >> a >> b) {
        std::cout << sum(a, b) << std::endl << std::endl;
    }
    return 0;
}

示例复杂度

时间复杂度：O(N)

空间复杂度：O(1)

题意分析

注意输出格式，是输出一行，空一行的形式，其他和A题一致

解题思路

将A题输出后面多一个换行即可。

H - A+B for Input-Output Practice (VIII)

题目

Your task is to calculate the sum of some integers.

你的任务是计算一些整数的和。

输入

Input contains an integer N in the first line, and then N lines follow. Each line starts with a integer M, and then M integers follow in the same line.

第一行输入包含一个整数N，然后是N行。每一行都以一个整数M开头，然后同一行有M个整数。

输出

For each group of input integers you should output their sum in one line, and you must note that there is a blank line between outputs.

对于每一组输入整数，应该在一行中输出它们的和，并且必须注意输出之间有一个空行。

示例

输入	输出
3	10
4 1 2 3 4
5 1 2 3 4 5	15
3 1 2 3
	6

示例代码

#include <iostream>

// 与D题相同的数组求和函数
int sum(int a[],int size) {
    for (int i = 1; i < size; i++)
        a[0] += a[i];
    return a[0];
}

int main(int argc, const char* argv[]) {
    int tasks;
    std::cin >> tasks;
    for (int i = 0; i < tasks; i++) {
        int n, a[20];
        std::cin >> n;
        for (int j = 0; j < n; j++)
            std::cin >> a[j];
        if (i == 0)
            std::cout << sum(a,n) << std::endl;
        else
            std::cout << std::endl << sum(a,n) << std::endl;
    }
    return 0;
}

示例复杂度

时间复杂度：O(n2)

空间复杂度：O(1)

题意分析

这次又是变了输入格式，注意每组示例的输入格式是先数据大小，再输入数据

解题思路

将E题的输入改成和题目一致

I - Download Manager

题目

Jiajia downloads a lot, a lot more than you can even imagine. Some say that he starts downloading up to 20,000 files together. If 20,000 files try to share a limited bandwidth then it will be a big hazard and no files will be downloaded properly. That is why, he uses a download manager.

If there are T files to download, the download manger uses the following policy while downloading files:

1. The download manager gives the smaller files higher priority, so it starts downloading the smallest n files at startup. If there is a tie, download manager chooses the one with less bytes remaining (for download). We assume that with at least 50 Mega Bytes/sec of bandwidth, n files can be downloaded simultaneously without any problem.

2. The available bandwidth is equally shared by the all the files that are being downloaded. When a file is completely downloaded its bandwidth is instantaneously given to the next file. If there are no more files left except the files that are being downloaded, this bandwidth is immediately shared equally by all remaining files that are being downloaded.

Given the size and completed percentage of each file, your task is to intelligently simulate the behavior of the download manager to find the total time required to download all the files.

佳佳下载了很多，比你想象的多得多。有人说他开始同时下载多达2万个文件。如果2万个文件试图共享有限的带宽，那么将是一个大的危险，没有文件将被正确下载。这就是他使用下载管理器的原因。

如果有T文件要下载，下载管理器在下载文件时使用以下策略:

1. 下载管理器给较小的文件更高的优先级，所以它在启动时开始下载最小的n文件。如果有一个并列，下载管理器会选择剩余字节较少的那个(用于下载)。我们假设有至少50兆字节/秒的带宽，n个文件可以同时下载而没有任何问题。

2. 可用带宽由正在下载的所有文件平均共享。当一个文件被完全下载后，它的带宽立即给了下一个文件。如果除了正在下载的文件之外没有其他文件，则该带宽立即被所有正在下载的剩余文件平均共享。

给定每个文件的大小和完成百分比，您的任务是智能地模拟下载管理器的行为，以找到下载所有文件所需的总时间。

输入

The will be at most 10 test cases. Each case begins with three integers T (1 <= T <= 20000), n (1 <= n <= 2000 and 1 <= n <= T) and B (50 <= B <= 1000). Here B denotes the total bandwidth available to Jiajia (In Megabytes/sec). Please note that the download manager always downloads n files in parallel unless there are less than n files available for download. Each of next T lines contains one non-negative floating-point number S (less than 20,000, containing at most 2 digits after the decimal places) and one integer P (0 <= P <= 100). These two numbers denote a file whose size is S megabyte and which has been downloaded exactly P% already. Also note that although theoretically it is not possible that the size of a file or size of its remaining part is a fraction when expressed in bytes, for simplicity please assume that such thing is possible in this problem. The last test case is followed by T=n=B=0, which should not be processed.

最多10个测试用例。每一种情况以三个整数开始T (1 <= T <= 20000)、n (1 <= n <= 2000和1 <= n <= T)和B (50 <= B <= 1000)。这里B表示佳佳可用的总带宽(兆字节/秒)。请注意下载管理器总是并行下载n个文件，除非可供下载的文件少于n个。下一个T行包含一个非负浮点数S(小于20000，小数点后最多包含2位)和一个整数P (0 <= P <= 100)。这两个数字表示一个文件的大小是S兆字节，并且已经下载了P%。还需要注意的是，虽然理论上一个文件的大小或其剩余部分的大小在以字节表示时不可能是一个分数，但为了简单起见，请假设在这个问题中这样做是可能的。最后一个测试用例后面是T=n=B=0，它不应该被处理。

输出

For each case, print the case number and the total time required to download all the files, expressed in hours and rounded to 2 digits after the decimal point. Print a blank line after the output of each test case.

对于每个案例，打印案例编号和下载所有文件所需的总时间，以小时表示，并在小数点后四舍五入到2位。在每个测试用例的输出后打印一个空行。

示例

输入	输出
6 3 90	Case 1: 0.66
100.00 90
40.40 70	Case 2: 0.00
60.30 70
40.40 80
40.40 85
40.40 88
1 1 56
12.34 100
0 0 0

Hint

Explanation

In the first sample, there are 6 files and the download manager can download 3 files simultaneously. The size of the smallest file is 40.40 Megabyte but there are
four such files (2nd, 4th, 5th and 6th files). So the download manager chooses the 6th, 5th and 4th files for download as they have less bytes remaining. All these
files get equal bandwidth (30.00 Megabyte/Sec). Of these three files the 8th file is finished first. So instantaneously the 2nd file starts downloading. Then, 5th file
is finished. So the next larger file (3rd file) starts downloading. This process goes on until all files are downloaded.

解释

在第一个示例中，有6个文件，下载管理器可以同时下载3个文件。最小的文件的大小是40.40兆字节，但有

4个这样的文件(第2、第4、第5、第6个文件)。因此，下载管理器选择第6、5和4个文件进行下载，因为它们剩下的字节较少。所有这些

文件得到相等的带宽(30.00兆字节/秒)。在这三个文件中，第8个文件首先完成。第2个文件瞬间开始下载。然后,5号文件

完成为止。所以下一个更大的文件(第三个文件)开始下载。这个过程一直持续到所有文件下载完毕。

示例代码

#include <iostream>

using namespace std;

// 获取还需要消耗的下载时间
double getDownloadTime(double fileSize, double downPart, double bandwidth) {
    double unDownSize,needDownTime; 
    unDownSize = fileSize * ((100 - downPart) * 0.01); // 完整文件大小乘以%x获得未下载的文件大小
    needDownTime = unDownSize / bandwidth; // 未下载文件大小除以带宽得到下载时间
    return needDownTime;
}

int main(int argc, const char* argv[]) {
    int T, n, B,ca = 1; // T表示下载的文件个数，n表示并行下载的数量，B表示带宽，ca是测试样例数
    while (~(scanf("%d %d %d",&T, &n, &B))) {
        double res = 0; // 存储每个样例的最终结果
        if (T == 0 && n == 0 && B == 0) break; // 退出条件，全等于零
        for (int i = 0; i < T; i++) {
            double size, part; // 每个文件的大小和已下载百分比
            scanf("%lf %lf", &size, &part);
            // 求和每个文件下载还需要消耗的时间
            res += getDownloadTime(size, part, B); 
        }
        // 根据格式输出
        printf("Case %d: %.2lf\n\n", ca, res);
        ca++; // 测试样例数
        res = 0; // 清空res的值，保证下一个样例不会出错
    }
    return 0;
}

示例复杂度

时间复杂度：O(logn)

空间复杂度：O(1)

题意分析

表面上看是模拟题，模拟一个下载器计算下载时间，实际上是计算题，需要我们找到公式将每个文件所需的下载时间求出来后进行求和。

解题思路

首先通过计算找到求文件下载时间的公式：

$$downTime = fileSize * (100 - downPart) * 0.01$$

随后根据公式求得所有文件的下载时间，并求和，最终公式如下：

$$result = \Sigma^{T}_{i=1} fileSize * (100 - downPart) * 0.01$$

J - sort

题目

给你n个整数，请按从大到小的顺序输出其中前m大的数。

输入

每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。

输出

对每组测试数据按从大到小的顺序输出前m大的数。

示例

输入	输出
5 3	213 92 3
3 -35 92 213 -644

示例代码

#include <iostream>
#include <algorithm>

using namespace std;

long long x[1000000]; // 根据范围确定的数组大小

// 给std::sort使用的比较函数
bool compare(int a, int b) {
    return a > b;
}

int main(int argc, const char* argv[]) {
    int n, m;
    while (~(scanf("%d %d", &n, &m))) { // 多样例输入
        for (int i = 0; i < n; i++) scanf("%lld",&x[i]);
        sort(x,x+n,compare); // std::sort从大到小排序
        for (int i = 0; i < m; i++) { // 输出排序后最大的前m个数，注意空格控制
            if (i == 0) printf("%lld",x[i]);
            else printf(" %lld",x[i]);
        }
        printf("\n");
    }   
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

long long x[1000000] = {0}; // 根据题目要求开大数组

// 因为C语言没有bool，采用int代替bool，用指针的方式计算出> == <
int compare (const void * a, const void * b)
{
    return ( *(long long*)b - *(long long*)a );
}

int main(int argc, const char* argv[]) {
    int n, m;
    while (~(scanf("%d %d", &n, &m))) { // 多样例输入
        for (int i = 0; i < n; i++) scanf("%lld",&x[i]);
        
        // 采用qsort排序，x是待排序的数组，n是要排序的数组大小，sizeof是数组内每个元素的大小，compare是比较函数
        qsort(x, n, sizeof(long long), compare);
        
        for (int i = 0; i < m; i++) { // 对输出进行格式化
            if (i == 0) printf("%lld",x[i]);
            else printf(" %lld",x[i]);
        }
        printf("\n");
    }
    return 0;
}

示例复杂度

时间复杂度：O(N)

空间复杂度：O(1)

题意分析

这个主要考虑排序算法的效率，冒泡，选择，插入全排序效率过低，部分排序可能也不太够，快速排序可能足够。同时注意多样例问题和空格要求。

解题思路

C语言采用qsort，C++采用std::sort排序，

K - 人见人爱A+B

题目

HDOJ上面已经有10来道A+B的题目了，相信这些题目曾经是大家的最爱，希望今天的这个A+B能给大家带来好运，也希望这个题目能唤起大家对ACM曾经的热爱。
这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。

输入

输入数据有多行组成，首先是一个整数N，表示测试实例的个数，然后是N行数据，每行有6个整数AH,AM,AS,BH,BM,BS，分别表示时间A和B所对应的时分秒。题目保证所有的数据合法。

输出

对于每个测试实例，输出A+B，每个输出结果也是由时分秒3部分组成，同时也要满足时间的规则（即：分和秒的取值范围在0~59），每个输出占一行，并且所有的部分都可以用32位整数表示。

示例

输入	输出
2	5 7 9
1 2 3 4 5 6	47 9 30
34 45 56 12 23 34

示例代码

#include <iostream>

using namespace std;

typedef struct ltime {
    int HH,MM,SS;
}lt; // 采用结构体方便存储时间数据

// 时间计算函数
lt timecalc(lt a, lt b) {
    lt res;
    // 先将所有时分秒求和
    res.HH = a.HH + b.HH;
    res.MM = a.MM + b.MM;
    res.SS = a.SS + b.SS;
    // 如果秒大于等于60，则分钟+1，秒减60，直到不满60
    while (res.SS >= 60) {
        res.MM++;
        res.SS -= 60;
    }
	// 分钟同理
    while (res.MM >= 60) {
        res.HH++;
        res.MM -= 60;
    }
    return res; // 最终返回计算后的结构体
}

int main(int argc, const char* argv[]) {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        lt aa,bb,res;
        cin >> aa.HH >> aa.MM >> aa.SS >> bb.HH >> bb.MM >> bb.SS; // 直接将六个数输入结构体
        res = timecalc(aa, bb); // 计算
        cout << res.HH << " " << res.MM << " " << res.SS << endl;
    }
    return 0;
}

示例复杂度

时间复杂度：O(N)

空间复杂度：O(1)

题意分析

这是让我们计算时间，根据时间的要求计算即可，小时直接相加，分钟和秒钟按60进制计算

解题思路

先把a和b两个时间加在一起，再看有没有超出范围的时间。

L - 人见人爱A-B

题目

参加过上个月月赛的同学一定还记得其中的一个最简单的题目，就是{A}+{B}，那个题目求的是两个集合的并集，今天我们这个A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）

呵呵，很简单吧？

输入

每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.
如果n=0并且m=0表示输入的结束，不做处理。

输出

针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.

示例

输入	输出
3 3 1 2 3 1 4 7	2 3
3 7 2 5 8 2 3 4 5 6 7 8	NULL
0 0

示例代码

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, const char* argv[]) {
    int n, m;
    while(cin >> n >> m) {
        int a[104], b[104], res[104], x = 0;
        if (n != 0 || m != 0) {
            for (int i = 0; i < n; i++)
                scanf("%d",&a[i]); // 输入第一个数组
            for (int i = 0; i < m; i++)
                scanf("%d",&b[i]); // 输入第二个数组
            
            for (int i = 0; i < n; i++) {
                bool flag = false;
                for (int j = 0; j < m; j++) {
                    if (a[i] == b[j]) {
                        flag = true; // 如果有重的就跳过这个数
                    }
                }
                if (!flag) { // 没有就给他存到新的数组里头
                    res[x] = a[i];
                    x++;
                }
            }

            if (x != 0) {
                sort(res,res+x); // 对新的数组进行排序
                for (int i = 0; i < x; i++)
                    printf("%d ",res[i]);
                cout << endl;
            }
            else cout << "NULL" << endl; // 如果没有结果就输出NULL
        }
        else break;
    }
    return 0;
}

示例复杂度

时间复杂度：O(N)

空间复杂度：O(1)

题意分析

这题是求集合的差集，即在A集合却不在B集合的数字的集合。因为两个都是集合，所以没有重复数字，不需要去重处理。

解题思路

将两个集合读取成数组后，利用双循环，每一个A数组中的数字都和B数组中的每一个数字比较，如果有存在相等的就抛弃。

M - 人见人爱A^B

题目

求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”

输入

输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。

输出

对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

示例

输入	输出
2 3	8
12 6	984
6789 10000	1
0 0

示例代码

#include <iostream>

using namespace std;

// b次方取n位的函数，k为取余值
int PowerGetLastNDight(int a, int b, int k) {
    int res = 1; // 因为要做乘法运算，所以结果变量初始化为1
    for (int i = 1; i <= b; i++) {
        res = res*a % 1000; // 循环进行自乘取余的过程
    }
    return res;
}

// 主函数
int main(int argc, const char* argv[]) {
    int a,b;
    while (cin >> a >> b) {
        if (a == 0 && b == 0) break;
        cout << PowerGetLastNDight(a,b,1000) << endl;
    }
    return 0;
}

示例复杂度

时间复杂度：O(Logn)

空间复杂度：O(1)

题意分析

题目意思很清晰，就是求a的b次方，取最后三位。但是由于b的数据很大，可能超限，所以不是math pow求法或者单纯的a*a循环b次的求法。

解题思路

这道题的破局关键在于这样一个公式：

​${(a ^ b)} \% k = \Sigma^{b}_{i = 1}a \% k$

当(a ^ b) 过大时，且需要取最后n位，就可以用这个公式，因为同等操作下，取余后求和后n位不变，因此，只要将操作数套用以上公式，便可在int范围内达成题目要求。