题解：P13837 GCD 与 LCM 问题 - 副本

Nebuloxia · 2025-08-27 12:27:32 · 题解

P13837 GCD 与 LCM 问题 题解

问题描述

给定正整数 a，需要找到三个正整数 b, c, d（均不超过 49999），满足：

解题思路

试将原问题分解为两种情况：

情况一：当 a 为奇数时

假设条件：

• \gcd(a, b) = 1

数学推导：

情况二：当 a 为偶数时

假设条件：

• \gcd(a, b) = 1

数学推导：

数学正确性证明

对于奇数 a：

由 \gcd(c, d) = 1 可得 \operatorname{lcm}(c, d) = c \times d，代入原方程：

整理得：

对于偶数 a：

由 \gcd(c, d) = 2 可得 \operatorname{lcm}(c, d) = \displaystyle\frac{c \times d}{2}，代入原方程：

整理得：

显然，b,c,d \le 49999，因此可以通过。

复杂度分析

• 时间复杂度：\operatorname{O}(T \times k)，其中 k 为平均枚举次数；
• 空间复杂度：\operatorname{O}(1)，只使用固定数量的变量。

算法实现代码

#include <bits/stdc++.h>
using namespace std;
int T, a, b, c, d, x;
int gcd(int x, int y){
    return y == 0 ? x : gcd(y, x % y);
}
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &a);
        if(a & 1){
            // 奇数情况：从 sqrt(1.1a) 开始枚举
            x = sqrt(1.1 * a);
            if(x == 1) x = 2;
            for(c = x; ; c++){
                d = (a + c) / (c - 1) + 1;
                b = c * d - c - d - a + 1;
                if(gcd(a, b) == 1 && gcd(c, d) == 1){
                    printf("%d %d %d\n", b, c, d);
                    break;
                }
            }
        }
        else{
            // 偶数情况：从 sqrt(2a) 开始枚举偶数
            x = sqrt(a << 1);
            if(x & 1) x++;
            if(x == 2) x = 4;
            for(c = x; ; c += 2){
                d = (a + c) / (c / 2 - 1) + 1;
                if(d & 1) d++;
                b = 1 + c * d / 2 - a - c - d;
                if(gcd(a, b) == 1 && gcd(c, d) == 2){
                    printf("%d %d %d\n", b, c, d);
                    break;
                }
            }
        }
    }
    return 0;
}