เราให้ตัวแปรอินพุตสามตัวเป็น 'start', 'end' และ 'number' เป้าหมายคือการหาคู่ของตัวเลขระหว่างจุดเริ่มต้นและจุดสิ้นสุดที่มีค่า 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 loop จาก i=start ถึง i<=end และ inner loop จาก j=start ถึง j<=end สำหรับแต่ละคู่ (i,j) ตรวจสอบว่า GCD(i,j)==number. ถ้านับเพิ่มจริง
-
นำตัวแปร 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 และตัวแปรจำนวน และส่งคืนคู่ระหว่างจุดเริ่มต้นและจุดสิ้นสุดที่มี gcd=number
-
นับเริ่มต้นเป็น 0
-
ใช้ two for loops สำหรับแต่ละสมาชิกของคู่ วงนอกจาก i=start ถึง i<=end และวงในจาก j=start ถึง j<=end.
-
ตรวจสอบว่าหาคู่ (i,j), GCD(i,j)==number. ถ้าเป็นจริง นับเพิ่ม
-
สุดท้ายเราจะได้จำนวนคู่ทั้งหมดที่มี gcd=number
-
ผลตอบแทนนับเป็นผลลัพธ์
แนวทางที่มีประสิทธิภาพ
ในแนวทางนี้ เราจะอัปเดตค่าของจุดเริ่มต้นและจุดสิ้นสุด สำหรับ pair(i,j) จะมี gcd=number ทั้ง i,j ควรหารด้วย ‘number. จะมีมากที่สุด (สิ้นสุด)/หมายเลข ที่จะแบ่ง 'หมายเลข' ทั้งหมด เพื่อให้ได้ตัวเลขระหว่างจุดเริ่มต้นและจุดสิ้นสุดที่หารด้วย 'ตัวเลข' เราจะสำรวจจากจุดเริ่มต้น =(เริ่มต้น + หมายเลข - 1) / หมายเลขไปยังจุดสิ้นสุด =สิ้นสุด / หมายเลข ดังนั้นสำหรับตัวเลขแต่ละตัวนั้น ถ้า gcd(i,j)==1 ให้นับเพิ่มขึ้นสำหรับคู่นั้น (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 และตัวแปรจำนวน และส่งคืนคู่ระหว่างจุดเริ่มต้นและจุดสิ้นสุดที่มี gcd=number
-
นับเริ่มต้นเป็น 0
-
ใช้ two for loops สำหรับแต่ละสมาชิกของคู่ วงนอกจาก i=start ถึง i<=end และวงในจาก j=start ถึง j<=end.
-
ตรวจสอบว่าคู่ (i,j), GCD(i,j)==1. ถ้าเป็นจริง นับเพิ่ม
-
สุดท้ายเราจะได้จำนวนคู่ทั้งหมดที่มี gcd=number
-
ผลตอบแทนนับเป็นผลลัพธ์
ตัวอย่าง (แนวทางไร้เดียงสา)
#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
