นับคู่จำนวนธรรมชาติที่มี GCD เท่ากับตัวเลขที่กำหนดใน C++

เราได้รับตัวแปรอินพุตสามตัวคือ 'start', 'end' และ 'number' เป้าหมายคือหาคู่ของตัวเลขระหว่าง start และ end ที่มีค่า GCD เท่ากับ 'number' เช่น GCD(A,B)=number และทั้ง A, B อยู่ในช่วง [start,end]

มาดูตัวอย่าง

อินพุต − start=5 end=20 number=8

เอาต์พุต − จำนวนคู่จำนวนธรรมชาติที่มี GCD เท่ากับตัวเลขที่กำหนด คือ 3

คำอธิบาย − คู่ระหว่าง 5 ถึง 20 ที่ GCD เป็น 8 คือ − (8,8), (8,16), (16,8)

อินพุต − start=5 end=20 number=7

เอาต์พุต − จำนวนคู่จำนวนธรรมชาติที่มี GCD เท่ากับตัวเลขที่กำหนด คือ 2

คำอธิบาย − คู่ระหว่าง 20 ถึง 30 ที่ GCD เป็น 7 คือ − (21,28), (28,21)

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

เราจะใช้สองวิธี วิธีแรกแบบง่ายที่เราจะเดินทางด้วยลูป FOR จาก i=start ถึง i<=end และลูปในจาก j=start ถึง j<=end สำหรับแต่ละคู่ (i,j) ตรวจสอบถ้า GCD(i,j)==number ถ้าจริงเพิ่ม count

• รับตัวแปร start, end, number เป็นจำนวนเต็ม
• ฟังก์ชัน GCD(int a, int b) แบบเรียกซ้ำ คืน GCD ของอาร์กิวเมนต์ a,b ที่ส่งมา
• ถ้า b ไม่เป็นศูนย์ เรียกตัวเองซ้ำเป็น GCD(b,a%b) มิฉะนั้นคืน a
• ฟังก์ชัน GCD_pairs(int start, int end, int number) รับตัวแปรขอบเขต start, end และตัวแปร number คืนคู่ระหว่าง start และ end ที่มี gcd=number
• กำหนด count เริ่มต้น 0
• ใช้ลูป FOR สองชั้นสำหรับแต่ละสมาชิกของคู่ ลูปนอกจาก i=start ถึง i<=end และลูปในจาก j=start ถึง j<=end
• ตรวจสอบถ้าสำหรับคู่ (i,j), GCD(i,j)==number ถ้าจริง เพิ่ม count
• ท้ายสุดเราจะได้จำนวนคู่ทั้งหมดที่มี gcd=number
• คืน count

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

ในแนวทางนี้ เราจะอัปเดตค่าของ start และ end สำหรับคู่ (i,j) ให้มี gcd=number ทั้ง i,j ควรหารด้วย 'number' ลงตัว จะมีสูงสุด (end-start)/number ตัวเลขที่จะหาร 'number' ลงตัว เพื่อรับตัวเลขระหว่าง start และ end ที่หาร 'number' ลงตัว เราจะเดินทางจาก start = (start + number - 1) / number ถึง end = end / number ดังนั้นสำหรับตัวเลขแต่ละตัว หาก gcd(i,j)==1 ให้เพิ่ม count สำหรับคู่ (i,j) นั้น

• รับตัวแปร start, end, number เป็นจำนวนเต็ม
• อัปเดต start = (start+number - 1)/number และ end=end/number
• ฟังก์ชัน GCD(int a, int b) แบบเรียกซ้ำ คืน GCD ของอาร์กิวเมนต์ a,b
• ถ้า b ไม่เป็นศูนย์ เรียกตัวเองซ้ำเป็น GCD(b,a%b) มิฉะนั้นคืน a
• ฟังก์ชัน GCD_pairs(int start, int end, int number) รับตัวแปรขอบเขต start, end และตัวแปร number คืนคู่ระหว่าง start และ end ที่มี gcd=number
• กำหนด count เริ่มต้น 0
• ใช้ลูป FOR สองชั้นสำหรับแต่ละสมาชิกของคู่ ลูปนอกจาก i=start ถึง i<=end และลูปในจาก j=start ถึง j<=end
• ตรวจสอบถ้าสำหรับคู่ (i,j), GCD(i,j)==1 ถ้าจริง เพิ่ม count
• ท้ายสุดเราจะได้จำนวนคู่ทั้งหมดที่มี gcd=number
• คืน count

ตัวอย่าง (วิธีง่าย)

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

int GCD(int a, int b){
    return b ? GCD(b, a % b) : a;
}

int GCD_pairs(int start, int end, int number){
    int count = 0;
    for (int i = start; i <= end; i++){
        for (int j = start; j <= end; j++){
            if (GCD(i, j) == number){
                count++;
            }
        }
    }
    return count;
}

int main(){
    int start = 10, end = 30, number = 10;
    cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of pairs of natural numbers with GCD equal to given number are: 7

ตัวอย่าง (แนวทางมีประสิทธิภาพ)

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

int GCD(int a, int b){
    return b ? GCD(b, a % b) : a;
}

int GCD_pairs(int start, int end, int number){
    int count = 0;
    for (int i = start; i <= end; i++){
        for (int j = start; j <= end; j++){
            if (GCD(i, j) == 1){
                count++;
            }
        }
    }
    return count;
}

int main(){
    int start = 10, end = 30, number = 10;
    start = (start + number - 1) / number;
    end = end / number;
    cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of pairs of natural numbers with GCD equal to given number are: 7