526互联

PAT Basic 1104. 天长地久

发布时间 2023-04-17 10:56:33作者: 十豆加日月

PAT Basic 1104. 天长地久

1. 题目描述：

“天长地久数”是指一个 \(K\) 位正整数 \(A\)，其满足条件为：\(A\) 的各位数字之和为 \(m\)，\(A+1\) 的各位数字之和为 \(n\)，且 \(m\) 与 \(n\) 的最大公约数是一个大于 2 的素数。本题就请你找出这些天长地久数。

2. 输入格式：

输入在第一行给出正整数 \(N\)（\(≤5\)），随后 \(N\) 行，每行给出一对 \(K\)（\(3<K<10\)）和 \(m\)（\(1<m<90\)），其含义如题面所述。

3. 输出格式：

对每一对输入的 \(K\) 和 \(m\)，首先在一行中输出 Case X，其中 X 是输出的编号（从 1 开始）；然后一行输出对应的 \(n\) 和 \(A\)，数字间以空格分隔。如果解不唯一，则每组解占一行，按 \(n\) 的递增序输出；若仍不唯一，则按 \(A\) 的递增序输出。若解不存在，则在一行中输出 No Solution。

4. 输入样例：

2
6 45
7 80

5. 输出样例：

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution

6. 性能要求：

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

思路：

根据题意，需要编写以下子函数：

  • isPrime()用于判断素数
  • getGCD()用于求解两数的最大公约数
  • getBitSum()用于求解正整数的各位数字之和
  • judgeForeverNum()用于天长地久数的逻辑判断

然后就是在main()函数中对各组 \(K\) 和 \(m\) 依次进行判断和输出，因为编写四个子函数已经累了，我就没按题意对解进行排序输出，并且不排序的结果也是符合测试用例的。。。第一次提交时testpoint2报wrong answer，testpoint3报time limit exceeded。。。额外定义结构体Ans存储解并排序后，通过了testpoint2，但是testpoint3依旧time limit exceeded。经过测试，当 \(K\) 取最大值9时，应该是依次遍历 \([10^8, 10^9-1]\) 每个数造成的超时，但是 \(K\) 取8就不会超时，比较直接的优化思路是当找到第一个满足数字之和为 \(m\) 的正整数 \(A\) 后，对 \(A\) 的各位数字重排列以及不同位数字+1，-1排列出所有的情况进行判断，但想想就头痛。。。

无奈参考大佬的题解：1104 天长地久 – PAT乙级真题_柳婼的博客-CSDN博客 ，直接一句话“由打表观察可得，所有天长地久数最后两位为”99″，那么将末尾的两个’9’隐藏后可直接带入暴力循环判断 ”，我人傻了，感觉智商被压制了QAQ。这里继续查找其他题解，得出此题的如下规律（前置条件是 \(A\) 的各位数字之和为 \(m\)，\(A+1\) 的各位数字之和为 \(n\)）：

  • 若 \(A\) 的末位数字不为9，那么 \(A+1\) 不会产生进位，则有 \(n=m+1\)，那么 \(GCD(m,n)=1\)，不满足题意，所以满足题意的 \(A\) 的末位数字一定为9。
  • 若 \(A\) 的倒数第二位数字不为9，那么 \(A+1\) 只会产生1次进位，则有 \(n=m+1-9=m-8\)，其中-9是因为末位数字由9变为0，那么 \(GCD(m,n) = 8\)，仍然不满足题意，所以满足题意的 \(A\) 的倒数第二位数字也一定为9。

通过以上规律即可得出满足题意的 \(A\) 的末尾两位一定为9，即可减少暴力循环的次数，减少耗时，通过testpoint3。

My Code:

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

// int isPrime(int num);
// int getGCD(int numA, int numB);
// int getBitSum(int num);
// int judgeForeverNum(int numLen, int sumA);

// // first submit testpoint2 wrong answer, testpoint3 time limit exceeded
// int main(void)
// {
//     int numCount=0;
//     int numLen=0, sumA=0;
//     int flag=0;
    
//     scanf("%d", &numCount);
//     for(int i=0; i<numCount; ++i)
//     {
//         scanf("%d%d", &numLen, &sumA);
//         printf("%d %d\n", numLen, sumA);
        
//         printf("Case %d\n", i+1);
        
//         flag = judgeForeverNum(numLen, sumA);
//         if(!flag) printf("No Solution\n");
        
//     }
    
    
//     return 0;
// }

// int isPrime(int num)
// {
//     if(num<=1) return 0; // 0 and 1 is not a prime
    
//     for(int i=2; i*i <= num; ++i)
//     {
//         if(num%i == 0)
//         {
//             return 0;
//         }
//     }
    
//     return 1;
// }

// int getGCD(int numA, int numB) // get the greatest common divisor of two number
// {
//     int remain=0;
    
//     while((remain=numA%numB))
//     {
//         numA = numB;
//         numB = remain;
//     }
    
//     return numB;
// }

// int getBitSum(int num) // get the sum of every bit of a number
// {
//     int tempSum=0;
    
//     while(num)
//     {
//         tempSum += num%10;
//         num /= 10;
//     }
    
//     return tempSum;
// }

// int judgeForeverNum(int numLen, int sumA)
// {
//     int leftBound=0, rightBound=0;
//     int flag=0; // flag of have solution
//     int tempM=1, tempN=1, tempGcd=0;
    
//     leftBound = pow(10, numLen-1);
//     rightBound = pow(10, numLen);
    
//     for(int i=leftBound; i<rightBound; ++i)
//     {
//         tempM = getBitSum(i);
        
//         if(tempM == sumA)
//         {
//             tempN = getBitSum(i+1);
//             tempGcd = getGCD(tempM, tempN);
//             if(tempGcd>2 && isPrime(tempGcd))
//             {
//                 printf("%d %d\n", tempN, i);
//                 flag = 1; // have solution
//             }
//         }
//     }
    
//     return flag;
// }



#include <stdio.h>
#include <math.h> // pow header
#include <stdlib.h> // qsort header

#define MAX_ANS 1000
typedef struct ans
{
    int n;
    int A;
} Ans;

int isPrime(int num);
int getGCD(int numA, int numB);
int getBitSum(int num);
int judgeForeverNum(int numLen, int sumA, Ans *pAns, int *ansCount);
int myCmp(const void *p1, const void *p2);

// first submit testpoint2 wrong answer, testpoint3 time limit exceeded
// after rectify, use qsort fixed testpoint2, testpoint3 still time limit exceeded
int main(void)
{
    int numCount=0;
    int numLen=0, sumA=0;
    int flag=0;
    Ans pAns[1000];
    int ansCount = 0;
    
    scanf("%d", &numCount);
    for(int i=0; i<numCount; ++i)
    {
        scanf("%d%d", &numLen, &sumA);
        //printf("%d %d\n", numLen, sumA);
        
        printf("Case %d\n", i+1);
        
        ansCount = 0;
        flag = judgeForeverNum(numLen, sumA, pAns, &ansCount);
        
        if(flag)
        {
            qsort(pAns, ansCount, sizeof(Ans), myCmp);
            for(int j=0; j<ansCount; ++j)
            {
                //printf("%d %d\n", pAns[j].n, pAns[j].A);
                printf("%d %d99\n", pAns[j].n, pAns[j].A);
            }
        }
        else
        {
            printf("No Solution\n");
        }
        
    }
    
    
    return 0;
}

int isPrime(int num)
{
    if(num<=1) return 0; // 0 and 1 is not a prime
    
    for(int i=2; i*i <= num; ++i)
    {
        if(num%i == 0)
        {
            return 0;
        }
    }
    
    return 1;
}

int getGCD(int numA, int numB) // get the greatest common divisor of two number
{
    int remain=0;
    
    while((remain=numA%numB))
    {
        numA = numB;
        numB = remain;
    }
    
    return numB;
}

int getBitSum(int num) // get the sum of every bit of a number
{
    int tempSum=0;
    
    while(num)
    {
        tempSum += num%10;
        num /= 10;
    }
    
    return tempSum;
}

int judgeForeverNum(int numLen, int sumA, Ans *pAns, int *ansCount)
{
    int leftBound=0, rightBound=0;
    int flag=0; // flag of have solution
    int tempM=1, tempN=1, tempGcd=0;
    
    // refer to https://blog.csdn.net/liuchuo/article/details/126209929
    // this fixed testpoint3
    numLen-=2;
    
    leftBound = pow(10, numLen-1);
    rightBound = pow(10, numLen);
    
    for(int i=leftBound; i<rightBound; ++i)
    {
        tempM = getBitSum(i);
        // refer to https://blog.csdn.net/liuchuo/article/details/126209929
        tempM+= 18;
        
        if(tempM == sumA)
        {
            tempN = getBitSum(i+1);
            tempGcd = getGCD(tempM, tempN);
            if(tempGcd>2 && isPrime(tempGcd))
            {
                pAns[*ansCount].n = tempN;
                pAns[*ansCount].A = i;
                ++(*ansCount);
                //printf("%d %d\n", tempN, i);
                flag = 1; // have solution
            }
        }
    }
    
    return flag;
}

int myCmp(const void *p1, const void *p2)
{
    Ans *pLeft = (Ans *)p1;
    Ans *pRight = (Ans *)p2;
    
    if(pLeft->n != pRight->n)
    {
        return (pLeft->n - pRight->n);
    }
    else // n is equal
    {
        return (pLeft->A - pRight->A);
    }
}