求乘N得M倍数的最小数 C++代码提交Dcoder失败排查

你在完成Dcoder平台Simple multiple problem编程挑战时，本地IDE运行编写的代码结果全部符合预期，但提交至平台后所有测试用例均判定失败，需要排查代码问题并给出改进方案。

题目规则 #

• 题目描述：给定两个数N和M，找到最小的正整数k，使得N与k的乘积是M的倍数
• 输入格式：第一行输入整数T，表示测试用例的数量；后续T行每行输入两个整数N和M
• 输出格式：对每个测试用例，输出符合要求的最小正整数k
• 约束条件：
  • 1 ≤ T ≤ 100
  • 1 ≤ N, M ≤ 10^6

样例输入 #

2
4 7
18 6

样例输出 #

7
1

#include <iostream>
using namespace std;

void find_smallest_number(int T, int **arr, int ans[]){
    for (int i=0; i<T; i++){
        for(int k=1; ; k++){
            if ((arr[i][0]*k) % arr[i][1] == 0){
                ans[i] = k;
                break;
            }
        }
    }
}

void clearMemory(int **arr, int T){
    for (int i = 0; i < T; i++){
        delete[] arr[i];
    }
    delete [] arr;
}

int main(){
    int T;
    //cout << "T = ";
    cin >> T;
    int ans[T];
    int **arr = new int *[T];
    for (int i = 0; i < T; i++) {
        arr[i] = new int [2];
    }
    for (int i=0; i<T; i++){
        //cout << "Case " << i+1 << ":\n";
        //cout << "N = ";
        cin >> arr[i][0];
        //cout << "M = ";
        cin >> arr[i][1];
    }

    find_smallest_number(T,arr,ans);

    for (int i=0; i<T; i++){
        cout << ans[i] << endl;
    }
    
    clearMemory(arr,T);
}

本地测试T=4，注释掉所有提示输出代码后，实际读取的输入流内容为：

4
4
7
18
6
3
21
54
4

本地运行得到的输出结果为：

7
1
7
2

原代码存在三个核心问题，是提交失败的主要原因：

1. 整数溢出：判断条件(arr[i][0]*k) % arr[i][1] == 0中，arr存储的是int类型变量，当N和M取到1e6的上限值、k也达到1e6量级时，N*k的结果会达到1e12，远超32位int类型最大2^31-1（约2e9）的存储范围，溢出后取模的计算结果完全错误，大数值测试用例全部无法通过。
2. 暴力枚举效率过低：从k=1开始逐个枚举的逻辑，在N和M互质且值为1e6时，需要循环1e6次才能得到结果，很容易触发平台的运行时间限制。
3. 非标准语法兼容问题：代码中int ans[T];属于变长数组，是GCC编译器的扩展语法，不属于标准C范畴，如果平台使用严格遵循C标准的编译器，会直接编译失败。

这道题可以直接用数论结论求解：最小正整数k = M / gcd(N, M)，其中gcd是N和M的最大公约数。原理是N*k要成为M的倍数，只需要补全N相对于M缺失的质因数即可，也就是把M除以两者的最大公约数，得到的就是最小的k，不需要暴力枚举，单次计算的时间复杂度仅为O(log(min(N,M)))，完全没有超时和溢出风险。

修正后的可提交代码如下：

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        long long N, M;
        cin >> N >> M;
        cout << M / gcd(N, M) << '\n';
    }
    return 0;
}

改进点说明 #

• 所有参与数值计算的变量统一使用long long类型，彻底规避整数溢出问题
• 用欧几里得算法求最大公约数，通过数学公式直接计算结果，相比暴力枚举效率提升万倍以上
• 去掉了不必要的二维指针动态内存分配，代码更简洁，不存在内存泄漏或内存管理错误
• 增加输入输出加速配置，避免大输入场景下的IO耗时超时
• 全部使用标准C++语法编写，不存在编译器兼容问题

内容的提问来源于stack exchange，提问作者Cakeice