专栏文章

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

NNebuloxia
P13837题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio41rt2
此快照首次捕获于
2025/12/02 13:01
3 个月前
此快照最后确认于
2025/12/02 13:01
3 个月前
查看原文

P13837 GCD 与 LCM 问题 题解

问题描述

给定正整数 aa，需要找到三个正整数 b,c,db, c, d（均不超过 4999949999），满足： a+b+c+d=gcd⁡(a,b)+lcm⁡(c,d)a + b + c + d = \gcd(a, b) + \operatorname{lcm}(c, d)

解题思路

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

情况一：当 aa 为奇数时

假设条件：
  • gcd⁡(a,b)=1\gcd(a, b) = 1
  • gcd⁡(c,d)=1\gcd(c, d) = 1（此时 lcm⁡(c,d)=c×d\operatorname{lcm}(c, d) = c \times d）
数学推导：
a+b+c+d=1+c×db=c×d−c−d−a+1\begin{align*} a + b + c + d &= 1 + c \times d \\ b &= c \times d - c - d - a + 1 \end{align*}

情况二：当 aa 为偶数时

假设条件：
  • gcd⁡(a,b)=1\gcd(a, b) = 1
  • gcd⁡(c,d)=2\gcd(c, d) = 2（此时 lcm⁡(c,d)=c×d2\operatorname{lcm}(c, d) = \displaystyle{\frac{c \times d}{2}}）
数学推导：
a+b+c+d=1+c×d2b=1+c×d2−a−c−d\begin{align*} a + b + c + d &= 1 + \frac{c \times d}{2} \\ b &= 1 + \frac{c \times d}{2} - a - c - d \end{align*}

数学正确性证明

对于奇数 aa：
由 gcd⁡(c,d)=1\gcd(c, d) = 1 可得 lcm⁡(c,d)=c×d\operatorname{lcm}(c, d) = c \times d，代入原方程： a+b+c+d=1+c×da + b + c + d = 1 + c \times d 整理得： b=c×d−c−d−a+1b = c \times d - c - d - a + 1
对于偶数 aa：
由 gcd⁡(c,d)=2\gcd(c, d) = 2 可得 lcm⁡(c,d)=c×d2\operatorname{lcm}(c, d) = \displaystyle\frac{c \times d}{2}，代入原方程： a+b+c+d=1+c×d2a + b + c + d = 1 + \displaystyle\frac{c \times d}{2} 整理得： b=1+c×d2−a−c−db = 1 + \displaystyle\frac{c \times d}{2} - a - c - d 显然，b,c,d≤49999b,c,d \le 49999，因此可以通过。

复杂度分析

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

算法实现代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...