AcWing 270. 最小公倍数 - C++ 代码详解与优化

#include #include #include

using namespace std;

const int N = 1000010;

int n; int primes[N], cnt; bool st[N];

int main() { cin >> n;

for (int i = 2; i <= n; i ++ )
{
    if (!st[i]) primes[cnt ++ ] = i;
    for (int j = 0; primes[j] <= n / i; j ++ )
    {
        st[primes[j] * i] = true;
        if (i % primes[j] == 0) break;
    }
}

int k = 0;
while (primes[k] <= n / primes[k])
{
    k ++ ;
}

int numerator = 1, denominator = 1;
for (int i = k - 1; i >= 0; i -- )
{
    int p = primes[i];
    int j = 1;
    while (p <= n)
    {
        j ++ ;
        p *= primes[i];
    }
    j -- ;

    if (j > 1)
    {
        while (j -- ) cout << primes[i] << ' ';
    }
    if (j == 1)
    {
        if (numerator * primes[i] < denominator * (primes[i] - 1))
        {
            numerator *= primes[i];
        }
        else denominator *= primes[i] - 1;
    }
}

if (numerator > denominator) swap(numerator, denominator);
cout << numerator << ' ' << denominator << endl;

return 0;

}

原因分析：

代码正确性问题：

1. 对于每个质数 $p$，计算它的最高次幂时，应该使用 $p^k \leq n$，而不是 $p^k \leq \lfloor \frac{n}{p} \rfloor$。
2. 在计算最小公倍数时，应该先判断 $a$ 和 $b$ 哪个更小，将其作为最终的输出，而不是固定将 $a$ 作为输出。

代码风格问题：

1. 建议使用更加具有描述性和表达性的变量名，比如将 $a$ 命名为 $numerator$，将 $b$ 命名为 $denominator$。

修改后的代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int primes[N], cnt;
bool st[N];

int main()
{
    cin >> n;

    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }

    int k = 0;
    while (primes[k] <= n / primes[k])
    {
        k ++ ;
    }

    int numerator = 1, denominator = 1;
    for (int i = k - 1; i >= 0; i -- )
    {
        int p = primes[i];
        int j = 1;
        while (p <= n)
        {
            j ++ ;
            p *= primes[i];
        }
        j -- ;

        if (j > 1)
        {
            while (j -- ) cout << primes[i] << ' ';
        }
        if (j == 1)
        {
            if (numerator * primes[i] < denominator * (primes[i] - 1))
            {
                numerator *= primes[i];
            }
            else denominator *= primes[i] - 1;
        }
    }

    if (numerator > denominator) swap(numerator, denominator);
    cout << numerator << ' ' << denominator << endl;

    return 0;
}