আমাদেরকে একটি ইনপুট 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) ফেরত দিন। শেষ পর্যন্ত আমরা জিসিডি মান পাই।
-
ফাংশন count_pairs(int N) N নেয় এবং জোড়ার সংখ্যা ফেরত দেয় যেমন জোড়ায়(A,B), B হল gcd এবং উভয়ই রেঞ্জে[1,N]।
-
এই ধরনের জোড়ার সংখ্যার জন্য গণনা =0 হিসাবে প্রাথমিক মান নিন।
-
জোড়ার প্রতিটি মানের জন্য, A এর জন্য লুপ i=1 থেকে i=N চালান এবং B এর জন্য লুপের জন্য j=1 t j=N নেস্টেড করুন।
-
একটি জোড়া (i,j) তৈরি করুন এবং GCD(i,j) এ পাস করুন। ফলাফল সমান হলে j. সংখ্যা বৃদ্ধি।
-
উভয় লুপের শেষে ফলাফল হিসাবে গণনা ফিরে আসে।
দক্ষ পদ্ধতি
যেমন আমরা দেখতে পাচ্ছি gcd(a,b)=b মানে a সর্বদা b এর গুণিতক। B(1<=b<=N) এর সমস্ত গুণিতক যেগুলি N-এর চেয়ে কম একটি জোড়া তৈরি করবে। একটি সংখ্যার জন্য i এর গুণিতক যদি তল (N/i) থেকে কম হয়।
-
ফাংশন count_pairs(int N) N নেয় এবং জোড়ার সংখ্যা ফেরত দেয় যেমন জোড়ায়(A,B), B হল gcd এবং উভয়ই রেঞ্জে[1,N]।
-
এই ধরনের জোড়ার সংখ্যার জন্য গণনা =0 হিসাবে প্রাথমিক মান নিন।
-
অস্থায়ী পরিবর্তনশীল temp=N এবং i=1.
নিন -
ব্যবহার করার সময় (i<=N) অনুসরণ করে
-
প্রতিটির জন্য আমি j=N/temp
হিসাবে গুণিতকের সীমা গণনা করি -
বর্তমানের জন্য জোড়ার সংখ্যা i হবে temp*(i-j+1)। গণনায় যোগ করুন।
-
i=j+1 সেট করুন। (A,B) পরবর্তী B এর জন্য।
-
পরবর্তী পুনরাবৃত্তির জন্য temp=N/i সেট করুন।
-
যখন লুপ শেষে, ফলাফল হিসাবে ফিরে গণনা.
উদাহরণ (নিষ্পাপ পদ্ধতি)
#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
