ค้นหาจำนวนศูนย์ต่อท้ายในฐาน B แทน N! ใช้ C++

ในบทความนี้ เราจะเข้าใจปัญหาในการค้นหาเลขศูนย์ต่อท้ายของจำนวนที่กำหนด 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 ซึ่งเท่ากับศูนย์ตามหลัง ด้วยวิธีนี้ เราสามารถคำนวณจำนวนศูนย์ต่อท้ายได้

แนวทางในการหาทางออก

เราได้กล่าวถึงวิธีการหาจำนวนศูนย์ต่อท้าย เราต้องหากำลังสูงสุดของ B ในแฟกทอเรียล N สมมติว่าฐาน B =14 จากนั้น 14 ในฐาน 14 จะแสดงเป็น 10 นั่นคือ (14)10 =(10)14 เป็นที่รู้จักกันว่าสูตรของ Legendre

โค้ด 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

คำอธิบายของโค้ดด้านบน

• ค้นหาพลังที่ใหญ่ที่สุดของฐานโดยใช้เวกเตอร์
• ในการคำนวณกำลังสูงสุด ให้คำนวณตัวประกอบเฉพาะโดยใช้เวกเตอร์เพื่อเก็บตัวประกอบเฉพาะทั้งหมด
• จากนั้นคำนวณกำลังขั้นต่ำของปัจจัยเฉพาะทั้งหมดของเบส
• สุดท้าย กำลังพิมพ์ผลลัพธ์

บทสรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนศูนย์ต่อท้ายในการแทนค่าฐาน B ของแฟกทอเรียล N ซึ่งเราแก้โดยใช้สูตรของ Legendre เรายังเขียนโค้ด C++ เพื่อแก้ปัญหาเดียวกัน คุณสามารถเขียนโค้ดนี้ในภาษาอื่นๆ เช่น Java, C, python เป็นต้น เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์