Chúng tôi được cung cấp một số num làm đầu vào. Mục đích là tìm số cặp dạng (i, j) sao cho ((num% i)% j)% num là cực đại và i và j đều nằm trong phạm vi [1, num].
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - num =4
Đầu ra - Đếm các cặp (i, j) sao cho ((n% i)% j)% n là cực đại là - 3
Giải thích - Các cặp sẽ là:(3,2), (3,3), (3,4)
Đầu vào - num =6
Đầu ra - Đếm các cặp (i, j) sao cho ((n% i)% j)% n là cực đại là - 4
Giải thích - Các cặp sẽ là:(4,3, (4,4), (4,5), (4,6)
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi sẽ giải quyết vấn đề này bằng hai cách tiếp cận. Trong cách tiếp cận đơn giản, giá trị phần dư lớn nhất có thể nhận được nếu chúng ta có num là một nửa của nó. Đặt nhiệt độ =num / 2 +1. Đặt phần còn lại tối đa là tổng =num% temp. Đảo ngược i, j từ 0 đến num và tìm i, j sao cho ((num% i)% j)% num ==tổng.
-
Lấy số đầu vào là số nguyên.
-
Hàm Maximum_pair (int num) nhận num và trả về số lượng các cặp (i, j) sao cho ((n% i)% j)% n là cực đại.
-
Lấy số lượng ban đầu là 0.
-
Giảm num xuống một nửa cho phần còn lại tối đa. Đặt nhiệt độ =((num / 2) + 1).
-
Tính phần còn lại tối đa dưới dạng tổng =num% temp;
-
Đối với các cặp (i, j). Đảo ngược bằng cách sử dụng hai vòng lặp for cho i và j trong phạm vi [1, num].
-
Nếu giá trị ((num% i)% j)% num bằng tổng, thì số gia tăng.
-
Kết quả là ở cuối cả hai vòng lặp for, trả về.
Phương pháp tiếp cận hiệu quả
Nhận phần còn lại tối đa là tổng =num% temp trong đó nhiệt độ là num / 2 + 1 . Bây giờ đối với cặp (i, j), chúng ta phải chọn i là num để nhận được phần dư lớn nhất. Chúng ta có thể chọn j từ tổng phạm vi đến num để tổng là tối đa. Vì vậy, tổng số các cặp sẽ là tổng số .
Trong trường hợp num =2 , trả về 4 vì các cặp sẽ là (1,1), (1,2), (2,1), (2,2) và sẽ không được tính bằng cách sử dụng tổng số.
-
Lấy số đầu vào là số nguyên.
-
Hàm Maximum_pair (int num) nhận num và trả về số lượng các cặp (i, j) sao cho ((n% i)% j)% n là cực đại.
-
Lấy số lượng ban đầu là 0.
-
Nếu num ==2, trả về 4.
-
Nếu không, giảm num xuống một nửa cho phần còn lại tối đa. Đặt nhiệt độ =((num / 2) + 1).
-
Tính phần còn lại tối đa dưới dạng tổng =num% temp;
-
Đặt số lượng =tổng số
-
Kết quả là cuối cùng trả về.
Ví dụ (cách tiếp cận ngây thơ)
#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<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6
Ví dụ (Phương pháp Tiếp cận 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<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6