Phân tích vấn đề để giải quyết bài toán

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 ≤ 10⁹

Ví dụ:

Số nhập vào là A	Số xuất ra là N
8	4
13	13

Giải:

Đặt vấn đề:
- Thông thường khi đọc xong đề bài này ta thường nghĩ ngay đến việc kiểm tra các số tự nhiên N với 1 ≤ N ≤ A để xem N^N có chia hết cho A hay không thì xuất ra giá trị cần tìm là N.

Vấn đề:

• Trong ngôn ngữ lập trình C/C++ ta có kiểu số nguyên dài nhất là 32 bit với số nguyên lớn nhất có thể lưu trữ là 2³² - 1 = 4294967295.
• Ta lại có 1 ≤ A ≤ 10⁹, giả sử N = 10⁹ thì khi tính N^N đã vượt quá giới hạn lưu trữ của máy.
• Ta nghĩ sang hướng giải quyết khác là dung kiểu số thực nhưng như thế ta lại không thể dung phép chia lấy phần dư (%) để chạy chương trình kiểm tra chia hết hay không.

- Vì vậy để giải quyết bài toán này ta phải dùng một cách khác.

Cách giải quyết bài toán:
- Theo định lí cơ bản của số học: Mọi số nguyên n > 1 đều biểu diễn được dưới dạng tích của các số nguyên tố. Phân tích này là duy nhất nếu không tính thứ tự của các thừa số. 
Như vậy mọi số nguyên n > 1 đều có thể biểu diễn dưới dạng $n = \prod\limits_{i = 1}^k {p_i^{{\alpha _i}}}  = p_1^{{\alpha _1}}p_2^{{\alpha _2}}...p_k^{{\alpha _k}},{\alpha _i} > 0$ trong đó p_i (i =1,2,…k) là những số nguyên tố đôi một khác nhau. Ta nói n có dạng phân tích chính tắc.

- Ta có hệ quả sau:

Nếu $n = \prod\limits_{i = 1}^k {p_i^{{\alpha _i}}} $, $m = \prod\limits_{i = 1}^k {p_i^{{\beta _i}}} $, ${\alpha _i},{\beta _i} \geqslant 0$ thì $m \vdots n$ $ \Leftrightarrow {\beta _i} \geqslant {\alpha _i}{\text{  }}(i = 1,2,...,k)$ (1)

- Do đó để giải quyết bài toán này ta sẽ phân tích A thành tích các thừa số nguyên tố của A (Trong đó trường hợp A = 1 ta sẽ xét riêng). Từ (1) ta có:

Với $A = p_1^{{\alpha _1}}p_2^{{\alpha _2}}p_3^{{\alpha _3}}....p_k^{{\alpha _k}}$ thì N phải có dạng $N = {p_1}{p_2}{p_3}...{p_k}$ $ \Rightarrow {N^N} = {({p_1}{p_2}{p_3}...{p_k})^N}$ đồng thời $N \geqslant Max\left[ {{a_i}} \right]$ $ \Rightarrow N = k.Tich$ với $Tich = {p_1}{p_2}{p_3}...{p_k}$.

Thuật toán:
- Phân tích A thành tích  của các thừa số.

• Đặt Tích bằng tích của các thừa số nguyên tố của A (với số mũ của mỗi số nguyên tố là 1)
• Gán Max[ai] là số mũ cao nhất trong các số mũ của các thừa số nguyên tố của A.

- Cho k chạy từ 1 cho đến khi $k.Tich \geqslant Max[ai]$ khi đó $N = k.Tich$. 

Source code:

#include <stdio.h>

#include <conio.h>

void main()

{

       unsigned long A, N, Tich, max, count, k;

       Tich = 1;

       k = 1;

       printf("Nhap vao so tu nhien A: ");

       scanf("%ld", &A);

       if (A == 1)

             N = 1;

       else

       {

             max = 1;

             for (int i=2; i*i<=A; i++)

             {

                    if (A % i == 0)

                    {

                           Tich = Tich*i;

                           count = 0;

                           while (A % i == 0)

                           {

                                 count++;

                                 A = A/i;

                           }

                           if (count > max)

                                 max = count;

                    }

             }

             if (A > 1)

                    Tich = Tich*A;

             while (k*Tich < max)

                    k++;

             N = k*Tich; 

       }

       printf("So tu nhien N can tim la: %ld\n", N);

       getch();

}