จำนวนคู่ (i, j) ที่ทำให้ ((n % i) % j) % n สูงสุดใน C++

เราได้รับตัวเลข num เป็นอินพุต เป้าหมายคือหาจำนวนคู่รูปแบบ (i,j) ที่ทำให้ ((num%i)%j)%num สูงสุด และ i และ j ทั้งคู่อยู่ในช่วง [1,num]

ตัวอย่าง

อินพุต - num=4

เอาต์พุต - จำนวนคู่ (i, j) ที่ทำให้ ((n % i) % j) % n สูงสุด คือ - 3

คำอธิบาย - คู่จะเป็น: (3,2), (3,3), (3,4)

อินพุต - num=6

เอาต์พุต - จำนวนคู่ (i, j) ที่ทำให้ ((n % i) % j) % n สูงสุด คือ - 4

คำอธิบาย - คู่จะเป็น: (4,3), (4,4), (4,5), (4,6)

แนวทางที่ใช้ในโปรแกรมด้านล่าง

เราจะแก้ปัญหานี้โดยใช้สองวิธี ในวิธี naïve ค่าที่เหลือสูงสุดสามารถได้หากเรามี num เป็นครึ่งหนึ่ง ตั้ง temp = num/2 + 1 ตั้งค่าที่เหลือสูงสุดเป็น total = num % temp เดินทางสำหรับ i,j จาก 0 ถึง num และหา i,j ที่ทำให้ ((num % i) % j) % num == total

• รับค่า num เป็นจำนวนเต็ม
• ฟังก์ชัน maximized_pair(int num) รับ num และคืนค่าจำนวนคู่ (i, j) ที่ทำให้ ((n % i) % j) % n สูงสุด
• ตั้งค่า count เริ่มต้นเป็น 0
• ลด num เหลือครึ่งหนึ่งสำหรับค่าที่เหลือสูงสุด ตั้ง temp = ((num / 2) + 1)
• คำนวณค่าที่เหลือสูงสุดเป็น total = num % temp
• สำหรับคู่ (i,j) เดินทางโดยใช้ลูป for สองอันสำหรับ i และ j ในช่วง [1,num]
• ถ้าค่า ((num % i) % j) % num เท่ากับ total ให้เพิ่ม count
• ที่สิ้นสุดของลูป for ทั้งสอง คืนค่า count เป็นผลลัพธ์

แนวทางที่มีประสิทธิภาพ (Efficient Approach)

ได้ ค่าที่เหลือสูงสุดเป็น total = num % temp โดยที่ temp คือ num/2+1 ตอนนี้สำหรับคู่ (i,j) เราต้องเลือก i เป็น num เพื่อให้ได้ค่าที่เหลือสูงสุด เราสามารถเลือก j จากช่วง total ถึง num เพื่อทำให้ total เป็นค่าสูงสุด ดังนั้นจำนวนคู่จะเป็น num-total

ในกรณี num=2 คืนค่า 4 เพราะคู่จะเป็น (1,1), (1,2), (2,1), (2,2) และจะไม่คำนวณได้ด้วย num-total

• รับค่า num เป็นจำนวนเต็ม
• ฟังก์ชัน maximized_pair(int num) รับ num และคืนค่าจำนวนคู่ (i, j) ที่ทำให้ ((n % i) % j) % n สูงสุด
• ตั้งค่า count เริ่มต้นเป็น 0
• ถ้า num==2 คืนค่า 4
• มิฉะนั้น ลด num เหลือครึ่งหนึ่งสำหรับค่าที่เหลือสูงสุด ตั้ง temp = ((num / 2) + 1)
• คำนวณค่าที่เหลือสูงสุดเป็น total = num % temp
• ตั้ง count = num - total
• ที่สิ้นสุด คืนค่า count เป็นผลลัพธ์

ตัวอย่าง (Naive Approach)

#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); 
}

เอาต์พุต

Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6

ตัวอย่าง (Efficient Approach)

#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); 
}

เอาต์พุต

Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6