Các Ước Số Gần Nhất Trong C++

Giả sử chúng ta có số nguyên num, tìm hai số nguyên có hiệu tuyệt đối nhỏ nhất mà tích bằng num+1 hoặc num+2. Trả về hai số bất kỳ thứ tự. Ví dụ: num = 8 → [3,3]. Với num+1=9, ước gần nhất là 3 và 3; num+2=10, ước gần nhất là 2 và 5; chọn 3 và 3.

Để giải quyết, chúng ta làm theo các bước:

• Định nghĩa getDiv(x): diff = vô cực, ret kích thước 2.

• Với i từ 1 đến sqrt(x): nếu x chia hết cho i: a = i, b = x/i; newDiff = |a-b|; nếu newDiff < diff: diff = newDiff; ret[0]=a, ret[1]=b.

• Trả về ret.

• Từ main: op1 = getDiv(num+1), op2 = getDiv(num+2); trả về op1 nếu |op1[0]-op1[1]| <= |op2[0]-op2[1]|, ngược lại op2.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}

class Solution {
public:
    vector <int> getDiv(int x){
        int diff = INT_MAX;
        vector <int> ret(2);
        for(int i = 1; i * i <= x; i++){
            if(x % i == 0){
                int a = i;
                int b = x / i;
                int newDiff = abs(a - b);
                if(newDiff < diff){
                    diff = newDiff;
                    ret[0] = a;
                    ret[1] = b;
                }
            }
        }
        return ret;
    }
    vector<int> closestDivisors(int num) {
        vector <int> op1 = getDiv(num + 1);
        vector <int> op2 = getDiv(num + 2);
        return abs(op1[0] - op1[1]) <= abs(op2[0] - op2[1]) ? op1 : op2;
    }
};

int main(){
    Solution ob;
    print_vector(ob.closestDivisors(8));
}

Đầu vào

8

Đầu ra

[3,3]