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

ในบทความนี้ เราจะเข้าใจปัญหาการหาจำนวนศูนย์ต่อท้าย (Trailing Zeroes) ของจำนวน N ในการแทนค่าแฟกทอเรียล (N!) ในฐาน B เช่น

Input : N = 7 Base = 2 Output : 4 Explanation : fact(7) = 5040 ในฐาน 10 และ 1001110110000 ในฐาน 2 มี 4 ศูนย์ต่อท้าย
Input : N = 11 Base = 5 Output : 2 Explanation : fact(11) = 39916800 ในฐาน 10 และ 40204314200 ในฐาน 5 มี 2 ศูนย์ต่อท้าย

ลองทบทวนกระบวนการแปลงเลขฐานสิบไปฐานอื่น เช่น การแปลง (5040)10 เป็น (?)2

คือการหารจำนวนด้วย 2 และเก็บเศษจนกว่าจะหารไม่ลง ผลลัพธ์คือเศษเรียงจากหลังมาหน้า

ผลคือ 4 ศูนย์ต่อท้าย ซึ่งเกิดเมื่อ 2 หารจำนวนลงตัว (เศษ 0)

การแยกตัวประกอบเฉพาะของ 5040 = 2⁴ × 56711 × 3381 × 181 หมายความว่า 2 หาร 5040 ลงตัว 4 ครั้ง เท่ากับจำนวนศูนย์ต่อท้าย

วิธีการแก้ปัญหา

เราต้องหกำลังสูงสุดของฐาน B ที่หาร N! ลงตัว ให้ฐาน B = 14 แล้ว 14 ในฐาน 14 จะเป็น 10 นั่นคือ (14)10 = (10)14 ซึ่งรู้จักในชื่อสูตรของเลจองดร (Legendre's Formula)

โค้ด C++ สำหรับวิธีการข้างต้น

นี่คือโค้ด C++ ที่ใช้แก้ปัญหานี้

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 

vector < pair < int, int >> primeFactorsofBase(int 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; 
    vector < pair < int, int >> prime_factors; 
    prime_factors = primeFactorsofBase(Base); 
    int result = INT_MAX; 
    for (int i = 0; i < prime_factors.size (); i++) { 
        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); 
    } 
    cout << "Number of trailing zeroes: " << result; 
    return 0; 
}

ผลลัพธ์

Number of trailing zeroes: 2

คำอธิบายโค้ด

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

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนศูนย์ต่อท้ายในฐาน B ของ N! โดยใช้สูตรของเลจองดร (Legendre's Formula) เรายังเขียนโค้ด C++ เพื่อแก้ปัญหานี้ สามารถนำไปใช้กับภาษาอื่น เช่น Java, C, Python ได้ หวังว่าจะเป็นประโยชน์