Tim N min de N^N chia het cho A

Bài 1: Cho số tự nhiên A. Hãy tìm số tự nhiên N nhỏ nhất sao cho N lũy thừa N (nhân N cho chính nó N lần) chia hết cho A. Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị: 1 ≤ A ≤ 109

Bài giải

I. Xác định yêu cầu
-   Input: 1 ≤ A ≤ 10⁹
-   Output: n_min  sao cho nⁿ chia hết cho A.

II. Đi tìm lời giải

-   Mới đọc đề thì các bạn thấy bài này khá là đơn giản vì chỉ cần dùng biến i chạy từ 1 tới a, nếu iⁱ chia hết cho a thì xuất n = i là xong bài toán, nhưng mọi chuyện không như ta mơ ước. Vì sao vậy test thử xem nào:

Với A = 1 --> N = 1
Với A = 2 --> N = 2
Với A = 3 --> N = 3
Với A = 101 --> N = ? 101¹⁰¹ ư? Đúng đó! Nhưng làm gì có kiểu dữ liệu nào trong C có thể lưu trữ con số khổng lồ đó, mà A của mình có thể chạy tới 1 tỉ luôn, ôi trời! Mới có 101 đã không ổn rồi, 1 tỉ thì sao nhỉ? Không thể nào tính được đúng không bạn. Vậy thì đành phá sản cách làm trên. Không sao chúng ta còn cách 2 bên dưới.

Thử suy luận kiểu này xem sao nhé:
Nếu a = 12 =2² * 3 thì để nⁿ chia hết cho 12 thì nⁿ phải chứa ít nhất: 2² * 3
Giả sử n = 2 * 3 (tích các thừa số nguyên tố của a) thì nⁿ = (2 * 3)^2*3 ở đây ta thấy rằng số mũ chỉ cần tới 2 là đủ để nⁿ chia hết cho a rồi, huống chi là    2 * 3. Hãy để ý tí nào 2 * 3 >= 2(số mũ lớn nhất)

Từ đó ta có thể suy ra cách giải như sau:
Gọi M = a.b.c…..z (tích các thừa số nguyên tố của a)
Chỉ cần tìm được một số nguyên tự nhiên i nhỏ nhất sao cho:
          i * M >= maxMu(số mũ lớn nhất của các thừa số nguyên tố)
Vậy thì n của chúng ta sẽ là: n = i * M


III. Source

// Library Declaration

#include <stdio.h>
#define Max 1000000000

// Prototype
void nhapA(long &a);
long tichThuaSoNgto(long a, int &max);  // ham tinh tich cac thua so nguyen to va so mu cao nhat
int timN(long M, int max);
// Main body
void main()
{
        // variable declaration
        long a;
        int max = 0;    // bien luu so mu cao nhat
        int n;         // n can tim

        // nhap vao a
        nhapA(a);
        // tinh tich thua so cac nguyen to luu vao bien M
        long M = tichThuaSoNgto(a, max);
        // tim n roi luu vao bien n
        n = timN(M, max);
        // xuat ra man hinh thong bao
        printf("\n%d la so nho nhat thoa: %d^%d chia het cho %ld\n\n", n, n, n, a);
}
// Function Definition
void nhapA(long &a)
{
        do
        {
                printf("\nNhap  0 < a <= 1000000000: ");
                scanf("%ld", &a);
        }
        while (a < 1 || a > Max);
}
long tichThuaSoNgto(long a, int &max)
{
        long p = 1; // tich cac thua so nguyen so cua a
        int i = 2;

        while (i <= a)
        {
                if (a % i == 0) // neu a chia het cho i, thi i la thua so nguyen to cua a. 
                {
                        p = p * i;      // vi the ta lay p nhan voi i, roi luu lai cho bien p
                        int dem = 0;    // bien luu so mu cua thua so nguyen to i

                        while (a % i == 0)
                        {
                                dem++;
                                a = a / i;
                        }
                        if (dem > max)  // neu so mu > max hien tai thi max = so mu do
                                max = dem;      
                }
                i++;
        }
        return p;
}
int timN(long M, int max)
{
        // chay i tu 1 toi khi ma bieu thuc: i * M >= max thoa.
        int i = 1;

        while (i * M < max)
                i++;

        return (i * M);
}

Mặc dù cố gắng nhưng sai sót là không thể tránh khỏi. Vì vậy rất mong nhận được góp ý từ các bạn đọc. Cảm ơn bạn đã giành thời gian đã đọc bài viết này.

Chúc Các Bạn Vui Vẻ!!!