Đếm số cặp (i, j) sao cho ((n % i) % j) % n được tối đa hóa trong C++

Cho một số num làm đầu vào. Mục tiêu là tìm số cặp dạng (i, j) sao cho ((num%i)%j)%num được tối đa hóa và cả i và j đều trong khoảng [1, num].

Ví dụ

Đầu vào - num=4

Đầu ra - Số cặp (i, j) sao cho ((n % i) % j) % n tối đa là 3

Giải thích - Các cặp: (3,2), (3,3), (3,4)

Đầu vào - num=6

Đầu ra - Số cặp (i, j) sao cho ((n % i) % j) % n tối đa là 4

Giải thích - Các cặp: (4,3), (4,4), (4,5), (4,6)

Phương pháp sử dụng

Chúng ta giải bằng hai cách. Cách đơn gián: giá trị dư lớn nhất đạt được khi chia num cho nửa của nó. Gán temp = num/2 + 1. Gán dư lớn nhất total = num % temp. Duyệt i, j từ 0 đến num tìm i, j sao cho ((num % i) % j) % num == total.

• Nhập num nguyên
• Hàm maximized_pair(int num) trả về số cặp
• Khởi tạo count = 0
• Giảm num xuống một nửa cho dư lớn nhất: temp = (num / 2) + 1
• Tính dư lớn nhất: total = num % temp
• Duyệt hai vòng lặp i, j trong [1, num]
• Nếu ((num % i) % j) % num == total, tăng count
• Trả về count

Cách hiệu quả (O(1))

Lấy dư lớn nhất total = num % temp với temp = num/2 + 1. Với cặp (i, j), ta chọn i = num để có dư lớn nhất. Chọn j từ khoảng total đến num để giữ total là lớn nhất. Số cặp sẽ là num - total.

Trường hợp num = 2, trả về 4 vì các cặp (1,1), (1,2), (2,1), (2,2) không tính bằng công thức num-total.

• Nhập num nguyên
• Hàm maximized_pair(int num) trả về số cặp
• Khởi tạo count = 0
• Nếu num == 2, trả về 4
• Ngược lại: temp = (num / 2) + 1, total = num % temp, count = num - total
• Trả về count

Chương trình minh họa (Cách đơn giản)

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

int maximized_pair(int num) {
    int count = 0;
    int temp = ((num / 2) + 1);
    int total = num % temp;
    for (int i = 1; i <= num; i++) {
        for (int j = 1; j <= num; j++) {
            int check = ((num % i) % j) % num;
            if (check == total)
                count++;
        }
    }
    return count;
}

int main() {
    int num = 10;
    cout << "Số cặp (i, j) sao cho ((n % i) % j) % n tối đa là: " << maximized_pair(num);
    return 0;
}

Đầu ra

Số cặp (i, j) sao cho ((n % i) % j) % n tối đa là: 6

Chương trình minh họa (Cách hiệu quả)

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

int maximized_pair(int num) {
    int count = 0;
    if (num == 2) {
        return 4;
    } else {
        int temp = ((num / 2) + 1);
        int total = num % temp;
        count = num - total;
    }
    return count;
}

int main() {
    int num = 10;
    cout << "Số cặp (i, j) sao cho ((n % i) % j) % n tối đa là: " << maximized_pair(num);
    return 0;
}

Đầu ra

Số cặp (i, j) sao cho ((n % i) % j) % n tối đa là: 6