นับจำนวนคู่ (A <=N, B <=N) โดยที่ gcd (A , B) เป็น B ใน C++

เราได้รับอินพุต N เป้าหมายคือการหาคู่ทั้งหมดของ A, B โดยที่ 1<=A<=N และ 1<=B<=N และ GCD(A, B) คือ B ทุกคู่มีค่ามากที่สุด ตัวหารร่วมเป็น B.

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − N=5

ผลผลิต − นับจำนวนคู่ (A <=N, B <=N) โดยที่ gcd (A , B) คือ B เท่ากับ − 10

คำอธิบาย

pairs (A <= N, B <= N) such that gcd (A , B) is B are −
(1,1), (2,1),(3,1),(4,1),(5,1),(2,2),(3,3),(4,2),(4,4), (5,5). Total 10.

ป้อนข้อมูล − N=50

ผลผลิต − นับจำนวนคู่ (A <=N, B <=N) โดยที่ gcd (A , B) เป็น B คือ − 207

คำอธิบาย

pairs (A <= N, B <= N) such that gcd (A , B) is B are :
(1,1), (2,1),(3,1),(4,1),(5,1).....(50,1)
(2,2),(3,3),(4,4).....(50,50)

คู่อื่นๆ เช่น (4,2), (6,3), (8,2),(8,4),...........(50,25) รวม 207

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

อาจมีหลายวิธีในการแก้ปัญหาที่กำหนด เช่น แนวทางไร้เดียงสาและแนวทางที่มีประสิทธิภาพ มาดูแนวทางไร้เดียงสากันก่อน .

• ใช้จำนวนเต็ม N เป็นอินพุต

• ฟังก์ชัน GCD(int A, int B) รับจำนวนเต็มสองจำนวนและส่งกลับตัวหารร่วมมากของ A และ B โดยจะคำนวณ gcd แบบเรียกซ้ำ

• หาก A หรือ B เป็น 0 ให้คืนค่าอื่น หากทั้งสองมีค่าเท่ากัน ให้คืนค่าใดค่าหนึ่งจากสองค่า ถ้า A>B กลับ (A-B,B) ถ้า B มากกว่า ให้คืนค่า gcd(B-A,A) ในที่สุดเราก็ได้ค่า gcd

• ฟังก์ชัน count_pairs(int N) รับ N และส่งกลับจำนวนคู่เพื่อให้เป็นคู่ (A,B), B คือ gcd และทั้งคู่อยู่ในช่วง[1,N]

• ใช้ค่าเริ่มต้นเป็น count =0 สำหรับจำนวนของคู่ดังกล่าว

• สำหรับแต่ละค่าของคู่ รัน for loop i=1 to i=N for A และ nested for loop j=1 t j=N for B.

• สร้างคู่ (i,j) และส่งต่อไปยัง GCD(i,j) ถ้าผลลัพธ์เท่ากับ j จำนวนที่เพิ่มขึ้น

• ที่ส่วนท้ายของทั้งสองลูปจะนับเป็นผลลัพธ์

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

อย่างที่เราเห็น gcd(a,b)=b หมายความว่า a เป็นจำนวนทวีคูณของ b เสมอ ทวีคูณดังกล่าวทั้งหมดของ b(1<=b<=N) ที่น้อยกว่า N จะสร้างคู่ สำหรับจำนวน i หากทวีคูณของ i น้อยกว่าชั้น (N/i) จะถูกนับ

• ฟังก์ชัน count_pairs(int N) รับ N และส่งกลับจำนวนคู่เพื่อให้เป็นคู่ (A,B), B คือ gcd และทั้งคู่อยู่ในช่วง[1,N]

• ใช้ค่าเริ่มต้นเป็น count =0 สำหรับจำนวนของคู่ดังกล่าว

• ใช้ตัวแปรชั่วคราว temp=N และ i=1

• ใช้ while (i<=N) ติดตาม

• สำหรับแต่ละฉันคำนวณขีด จำกัด ของทวีคูณเป็น j=N/temp

• จำนวนคู่สำหรับปัจจุบัน i จะเป็น temp*(i-j+1) เพิ่มนับ

• ตั้งค่า i=j+1 สำหรับ B ถัดไปของ (A,B)

• ตั้งค่า temp=N/i สำหรับการทำซ้ำครั้งต่อไป

• ในตอนท้ายของลูป while ให้นับผลลัพธ์กลับมา

ตัวอย่าง(วิธีการไร้เดียงสา)

#include <iostream>
using namespace std;
int GCD(int A, int B){
   if (A == 0){
      return B;
   }
   if (B == 0){
      return A;
   }
   if (A == B){
      return A;
   }
   if (A > B){
      return GCD(A-B, B);
   }
   return GCD(A, B-A);
}
int count_pairs(int N){
   int count = 0;
   for(int i=1; i<=N; i++){
      for(int j = 1; j<=N; j++){
         if(GCD(i, j)==j){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int N = 4;
   cout<<"Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: "<<count_pairs(N);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8

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

#include <bits/stdc++.h>
using namespace std;
int Count_pairs(int N){
   int count = 0;
   int temp = N;
   int i = 1;
   while(i <= N){
      int j = N / temp;
      count += temp * (j - i + 1);
      i = j + 1;
      temp = N / i;
   }
   return count;
}
int main(){
   int N = 4;
   cout<<"Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: "<<Count_pairs(N);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8