আমরা তিনটি ইনপুট ভেরিয়েবল দিয়েছি 'শুরু', 'শেষ' এবং 'সংখ্যা'। লক্ষ্য হল শুরু এবং শেষের মধ্যে সংখ্যার জোড়া খুঁজে বের করা যার GCD মান 'সংখ্যা'-এর সমান। যেমন GCD(A,B)=সংখ্যা এবং A, B উভয়ই পরিসরে [শুরু, শেষ]।
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − শুরু=5 শেষ=20 সংখ্যা=8
আউটপুট − প্রদত্ত সংখ্যার সমান GCD সহ প্রাকৃতিক সংখ্যার জোড়ার সংখ্যা হল − 3
ব্যাখ্যা − 5 থেকে 20 এর মধ্যে জোড়া যেমন GCD 8 হয় − (8,8), (8,16), (16,8)
ইনপুট − শুরু=5 শেষ=20 সংখ্যা=7
আউটপুট − প্রদত্ত সংখ্যার সমান GCD সহ প্রাকৃতিক সংখ্যার জোড়ার সংখ্যা হল − 2
ব্যাখ্যা − 20 থেকে 30 এর মধ্যে জোড়া যেমন GCD হল 7 হল − (21,28), (28,21)
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
আমরা দুটি পন্থা ব্যবহার করব। প্রথম নিরীহ পদ্ধতি যেখানে আমরা i=start থেকে i<=end পর্যন্ত লুপ ব্যবহার করে এবং j=start থেকে j<=end পর্যন্ত ভিতরের লুপ ব্যবহার করব। প্রতিটি জোড়া(i,j) এর জন্য GCD(i,j)==সংখ্যা আছে কিনা তা পরীক্ষা করুন। যদি সত্য বৃদ্ধির সংখ্যা।
-
ভেরিয়েবলের শুরু, শেষ এবং সংখ্যাকে পূর্ণসংখ্যা হিসাবে নিন।
-
ফাংশন GCD(int a, int b) পুনরাবৃত্তিমূলক এবং এটিতে পাস করা আর্গুমেন্ট a,b এর GCD ফেরত দেয়।
-
যদি b অ-শূন্য হয় তবে এটি নিজেকে পুনরাবৃত্তভাবে GCD(b,a%b) বলে ডাকে অন্যথায় এটি a ফেরত দেয়।
-
ফাংশন GCD_pairs(int start, int end, int number) বাউন্ডারি ভেরিয়েবল স্টার্ট, এন্ড এবং ভ্যারিয়েবল সংখ্যা নেয় এবং শুরু এবং শেষের মধ্যে জোড়া দেয় যার gcd=number আছে।
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
জোড়ার প্রতিটি সদস্যের জন্য লুপের জন্য দুটি ব্যবহার করা। i=start থেকে i<=end পর্যন্ত বাইরের লুপ এবং j=start থেকে j<=end পর্যন্ত।
-
জোড়া (i,j), GCD(i,j)==সংখ্যার জন্য কিনা পরীক্ষা করুন। সত্য হলে, সংখ্যা বৃদ্ধি করুন।
-
অবশেষে আমরা gcd=number সহ জোড়ার মোট গণনা পাব।
-
ফলাফল হিসাবে রিটার্ন গণনা।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা শুরু এবং শেষের মান আপডেট করব। জোড়া(i,j)-এর জন্য gcd=সংখ্যার জন্য, i,j উভয়ই 'সংখ্যা দ্বারা বিভাজ্য হওয়া উচিত। সেখানে সর্বাধিক (শেষ-শুরু)/সংখ্যা নং থাকবে যা 'সংখ্যা'কে সম্পূর্ণরূপে ভাগ করবে। 'সংখ্যা' দ্বারা বিভাজ্য শুরু এবং শেষের মধ্যে সংখ্যা পাওয়ার জন্য, আমরা শুরু =(শুরু + সংখ্যা - 1) / সংখ্যা থেকে শেষ =শেষ / সংখ্যা অতিক্রম করব; তাই প্রতিটি সংখ্যার জন্য যদি gcd(i,j)==1 তাহলে এই ধরনের জোড়ার জন্য সংখ্যা বৃদ্ধি (i,j)।
-
ভেরিয়েবলের শুরু, শেষ এবং সংখ্যাকে পূর্ণসংখ্যা হিসাবে নিন।
-
আপডেট স্টার্ট =(শুরু + সংখ্যা - 1)/সংখ্যা। এবং শেষ=শেষ/সংখ্যা।
-
ফাংশন GCD(int a, int b) পুনরাবৃত্তিমূলক এবং এটিতে পাস করা আর্গুমেন্ট a,b এর GCD ফেরত দেয়।
-
যদি b অ-শূন্য হয় তবে এটি নিজেকে পুনরাবৃত্তভাবে GCD(b,a%b) বলে ডাকে অন্যথায় এটি a ফেরত দেয়।
-
ফাংশন GCD_pairs(int start, int end, int number) বাউন্ডারি ভেরিয়েবল স্টার্ট, এন্ড এবং ভ্যারিয়েবল সংখ্যা নেয় এবং শুরু এবং শেষের মধ্যে জোড়া দেয় যার gcd=number আছে।
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
জোড়ার প্রতিটি সদস্যের জন্য লুপের জন্য দুটি ব্যবহার করা। 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
