এই নিবন্ধে, আমরা একটি প্রদত্ত সংখ্যা N এর অনুগামী শূন্য খুঁজে পাওয়ার সমস্যাটি বুঝতে পারব এর ফ্যাক্টরিয়ালের ভিত্তি B উপস্থাপনায়। উদাহরণের জন্য
Input : N = 7 Base = 2 Output : 4 Explanation : fact(7) = 5040 in base10 and 1001110110000 in base16 having 4 trailing zero. Input : N = 11 Base = 5 Output : 2 Explanation : fact(11) = 39916800 in base10 and 40204314200 in base16 having 2 trailing zeroes.
আসুন প্রথমে যেকোন দশমিক সংখ্যাকে একটি বেস থেকে অন্যটিতে রূপান্তর করার প্রক্রিয়াটি সংক্ষেপে দেখি। আসুন (5040)10 থেকে (?)2
রূপান্তর করার একটি উদাহরণ নেওয়া যাক
অর্থাৎ, সংখ্যাটিকে 2 দ্বারা ভাগ করা এবং অবশিষ্টটি রাখা যতক্ষণ না সংখ্যাটিকে আরও ভাগ করা যায় না। ফলাফল বিপরীত ক্রমে অবশিষ্ট হবে।
ফলস্বরূপ, আমাদের কাছে 4টি অনুগামী শূন্য রয়েছে, এবং এই অনুগামী শূন্যটি আমরা পেয়েছি যখন 2 সংখ্যাটিকে অবশিষ্ট 0 দিয়ে ভাগ করে।
5040 =24 * 56711 * 3381 * 181 এর প্রাইম ফ্যাক্টরাইজেশন মানে 2 ভাগ করে 5040 কে 4 বার বাকি 0 দিয়ে যা ট্রেলিং শূন্যের সমান। এইভাবে, আমরা পরবর্তী শূন্যের সংখ্যা গণনা করতে পারি।
সমাধান খোঁজার পদ্ধতি
আমরা উপরের শূন্যের সংখ্যা বের করার উপায় নিয়ে আলোচনা করেছি। আমাদের ফ্যাক্টোরিয়াল N-এ B-এর সর্বোচ্চ শক্তি খুঁজে বের করতে হবে, ধরা যাক বেস B =14, তাহলে বেস 14-এ 14-কে 10 হিসাবে দেখানো হবে, অর্থাৎ (14)10 =(10)14। এটি কিংবদন্তির সূত্র নামেও পরিচিত।
উপরের পদ্ধতির জন্য C++ কোড
এখানে C++ সিনট্যাক্স রয়েছে যা আমরা প্রদত্ত সমস্যার সমাধান করতে ইনপুট হিসাবে ব্যবহার করতে পারি −
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
vector < pair < int, int >> primeFactorsofBase(int Base) {
// declaring factors to store prime factors
// along with occurence in factorisation of Base .
vector < pair < int, int >>factors;
for (int i = 2; Base != 1; i++) {
if (Base % i == 0) {
int count = 0;
while (Base % i == 0){
Base = Base / i;
count++;
}
factors.push_back (make_pair (i, count));
}
}
return factors;
}
int main () {
int N = 11, Base = 5;
// finding the largest power of Base that divides factorial N.
vector < pair < int, int >>prime_factors;
// finding prime factors by primeFactorsofBase() function.
prime_factors = primeFactorsofBase(Base);
int result = INT_MAX;
for (int i = 0; i < prime_factors.size (); i++) {
// calculating minimum power.
int count = 0;
int r = prime_factors[i].first;
while (r <= N){
count += (N / r);
r = r * prime_factors[i].first;
}
result = min (result, count / prime_factors[i].second);
}
//printing trailing zeroes stored in result.
cout << "Number of trailing zeroes: " <<result;
return 0;
} আউটপুট
Number of trailing zeroes: 2
উপরের কোডের ব্যাখ্যা
- ভেক্টর ব্যবহার করে বেসের সবচেয়ে বড় শক্তি খুঁজুন।
- সবচেয়ে বড় শক্তি গণনা করতে, সমস্ত মৌলিক গুণনীয়ক সংরক্ষণ করতে ভেক্টর ব্যবহার করে প্রাইম ফ্যাক্টর গণনা করুন।
- তারপর বেসের সমস্ত মৌলিক গুণনীয়কের ন্যূনতম শক্তি গণনা করুন।
- অবশেষে, ফলাফল প্রিন্ট করা হচ্ছে।
উপসংহার
এই নিবন্ধে, আমরা ফ্যাক্টোরিয়াল N-এর বেস B উপস্থাপনায় অনুগামী শূন্যের সংখ্যা খুঁজে বের করার সমস্যাটি সমাধান করি, যা আমরা Legendre-এর সূত্র ব্যবহার করে সমাধান করি। একই সমস্যা সমাধানের জন্য আমরা C++ কোডও লিখি। আপনি এই কোডটি জাভা, সি, পাইথন ইত্যাদির মতো অন্য যেকোনো ভাষায় লিখতে পারেন। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে।
