小水题求解（被卡5个月确信）

问题讨论区 普及段
1

最小公倍数

提交(Submit)

中文 切换语言(Change Language)

时间：0.2 空间：32M

题目描述：

给你三个数a,b,L,求最小的c满足LCM(a,b,c)=L

输入格式：

输入三个整数a,b,L

输出格式：

输出一个整数

样例输入1：

3 5 30

样例输出1：

2

样例输入2：

209475 6992 77086800

样例输出2：

1

样例输入3：

2 6 10

样例输出3：

impossible

约定：

1<=a<=b<=106,1<=L<=1012

提示：

写不了一点

1 个赞
2 
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
int main() {
    int a, b, L;
    cin >> a >> b >> L;
    // 如果 L 不能被 lcm(a, b) 整除，则无解
    if (L % lcm(a, b) != 0) {
        cout << "impossible" << endl;
        return 0;
    }
    int l = lcm(a, b);
    int c = L / l;
    int ans = numeric_limits<int>::max();
    // 尝试所有可能的 c 值
    for (int i = 1; i * i <= c; ++i) {
        if (c % i == 0) {
            int temp = i;
            if (lcm(l, i) == L) {
                ans = min(ans, temp);
            }
            temp = c / i;
            if (temp != i && lcm(l, temp) == L) {
                ans = min(ans, temp);
            }
        }
    }
    if (ans == numeric_limits<int>::max()) {
        cout << "impossible" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

试试？

2 个赞
3

@金彦劭 WA20（悲）

这题有没有什么公式可以推的？

1 个赞
4

咋感觉 AI 写出来的

2 个赞
5

nonono

1 个赞
6

好像要高精

1 个赞
7

此帖子已被社区举报，现已被临时隐藏。

8

之前没注意到，现在看到了。

回老帖？该罚！

@huangfeidong 警告一次

1 个赞
9