C++에서 gcd(A , B)가 B가 되도록 쌍(A <=N, B <=N)의 수를 센다.

<시간/>

입력 N이 주어집니다. 목표는 1<=A<=N 및 1<=B<=N 및 GCD(A, B)가 B가 되도록 A, B의 모든 쌍을 찾는 것입니다. 모든 쌍은 공약수 B.

예를 들어 이해합시다.

입력 - N=5

출력 − gcd(A , B)가 B가 되도록 쌍(A <=N, B <=N)의 개수를 셉니다. − 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

출력 − gcd(A , B)가 B가 되는 쌍(A <=N, B <=N)의 개수를 셉니다. − 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을 취하고 pair(A,B)에서 B가 gcd이고 둘 다 [1,N] 범위에 있도록 쌍의 수를 반환합니다.
이러한 쌍의 수에 대해 초기 값을 count =0으로 취하십시오.
쌍의 각 값에 대해 루프 i=1에서 A에 대해 i=N까지 실행하고 B에 대해 루프 j=1 t j=N에 대해 중첩합니다.
쌍(i,j)을 만들고 GCD(i,j)에 전달합니다. 결과가 j와 같으면. 증분 수.
두 루프의 끝에서 결과로 count를 반환합니다.

효율적인 접근

우리가 볼 수 있듯이 gcd(a,b)=b는 a가 항상 b의 배수임을 의미합니다. N보다 작은 b(1<=b<=N)의 모든 배수는 쌍을 만듭니다. 숫자 i의 경우 i의 배수가 floor(N/i)보다 작으면 계산됩니다.

count_pairs(int N) 함수는 N을 취하고 pair(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로 설정합니다. (A,B)의 다음 B를 위해.
다음 반복을 위해 temp=N/i를 설정합니다.
while 루프가 끝나면 결과로 count를 반환합니다.

예시(순진한 접근)

#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