1103 缘分数 – PAT乙级真题

所谓缘分数是指这样一对正整数 a 和 b，其中 a 和它的小弟 a−1 的立方差正好是另一个整数 c 的平方，而 c 正好是 b 和它的小弟 b−1 的平方和。例如 83−73=169=132，而 13=32+22，于是 8 和 3 就是一对缘分数。

给定 a 所在的区间 [m,n]，是否存在缘分数？

输入格式：

输入给出区间的两个端点 0<m<n≤25000，其间以空格分隔。

输出格式：

按照 a 从小到大的顺序，每行输出一对缘分数，数字间以空格分隔。如果无解，则输出 No Solution。

输入样例 1：

8 200

输出样例 1：

8 3
105 10

输入样例 2：

9 100

输出样例 2：

No Solution

分析：遍历m到n区间中的每一个数a，先判断a和它的小弟a-1的立方差d是不是一个平方数，sqrt(d) * sqrt(d) == d则说明其是一个平方数，然后从1开始枚举这个数是不是另外两个数b和b-1的平方和，如果b和b-1的平方和等于a和a-1的立方差的平方根，则输出a和b，并将flag置为1，如果最后flag都为0，则输出No Solution~
这里用映射map<long long, long long> record记录了每一个数b和b-1的平方和的结果，后续如果有碰到之前计算过的平方和，就直接调用map中的结果，不用再次计算~

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
long long m, n, a, b, d, c, flag, temp;
map<long long, long long> record;
int main() {
    cin >> m >> n;
    for (a = m; a <= n; a++) {
        d = a * a * a - (a-1) * (a-1) * (a-1), c = sqrt(d);
        if (c * c != d) continue;
        for (long long b = 1; b < c; b++) {
            if (record.count(b)) temp = record[b];
            else {
                temp = b * b + (b - 1) * (b - 1);
                record[b] = temp;
            }
            if (temp == c) {
                cout << a << ' ' << b << '\n';
                flag = 1;
                break;
            }
        }
    }
    if (!flag) cout << "No Solution";
    return 0;
}

#include <iostream>

#include <map>

#include <cmath>

using namespace std;

long long m, n, a, b, d, c, flag, temp;

map<long long, long long> record;

int main() {

cin >> m >> n;

for (a = m; a <= n; a++) {

d = a * a * a - (a-1) * (a-1) * (a-1), c = sqrt(d);

if (c * c != d) continue;

for (long long b = 1; b < c; b++) {

if (record.count(b)) temp = record[b];

else {

temp = b * b + (b - 1) * (b - 1);

record[b] = temp;

}

if (temp == c) {

cout << a << ' ' << b << '\n';

flag = 1;

break;

}

if (!flag) cout << "No Solution";

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版