PAT Basic 1103. 缘分数

1. 题目描述：

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

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

2. 输入格式：

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

3. 输出格式：

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

4. 输入样例：

8 200

9 100

5. 输出样例：

8 3
105 10

No Solution

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

根据给定区间遍历判断是否存在缘份数\(a\)，\(b\)。其中缘分数的判断根据题意编写即可，要注意以下几个点：

\(c\) 一定要是个整数，不是整数的话直接退出判断。
因为\(c=b^2+(b-1)^2\)，而正整数\(b\ge1\)，所以\(c\ge b^2\)，进而有\(c \ge b\)，当\(b=1\)时等号成立，根据这个条件遍历 \(b\) 的每一种可能进行判断。

第一次提交时testpoint4报wrong answer，考虑边界情况，当\(a=1\)时，有\(a=b=c=1\)，也符合缘分数的定义，题目没有说明 \(a\)，\(b\) 一定不同，但是说明了 \(c\) 是另一个整数，即 \(a \ne c\)，所以应该排除 \(a=1,b=1\) 的情况，加上这部分逻辑判断后AC。

My Code:

#include <stdio.h>
#include <math.h> // pow header, sqrt header

int judgeLotNum(int a);

// first submit testpoint4 wrong answer
int main(void)
{
    int leftBound=0, rightBound=0;
    int flag=0;
    
    scanf("%d%d", &leftBound, &rightBound);
    
    for(int i=leftBound; i<=rightBound; ++i)
    {
        if(judgeLotNum(i)) flag = 1;
    }
    
    if(!flag) printf("No Solution\n");
    
    return 0;
}

int judgeLotNum(int a) // return 1 means have lot number, 0 means doesn't have
{
    int c2 = pow(a,3) - pow(a-1, 3);
    int c = sqrt(c2);
    int b=0;
    
    if(a==1) return 0; // a == 1 == c == b is not a solution, this fixed testpoint4
    if(c*c != c2) return 0; // if c is not a integer, return directly
    
    for(int i=1; i<=c; ++i)
    {
        b = i;
        if((b*b + (b-1)*(b-1)) == c)
        {
            printf("%d %d\n", a, b); // output lot number
            return 1;
        }
    }
    
    return 0;
}