Bài tập nghiên cứu 1

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

Phân tích bài toán:

Ở đây, bài toán muốn tìm một số N nhỏ nhất sao N^N chia hết cho A.

Dễ nhận thấy rằng N tối đa không thể vượt quá A vì A cũng là một số thỏa yêu cầu. Nếu ta cho chạy tuần tự N, rồi kiểm tra xem N^N có chia hết cho A thì cho ra kết quả là N, thì đây là một phương pháp cực kỳ thất sách, vì việc tính N^N không hề đơn giản. N^N là số vô cùng lớn,  chỉ với N=10 thì N^N đã là 10 tỉ, huống hồ nhiều trường hợp cho ra kết quả N rất lớn, ngay cả việc dùng mảng lưu trữ cũng trở nên khó khăn khi thực hiện với N khoản vài trăm.
Vì vậy, cần nghĩ tới một hướng đi mà không cần tính N^N mà vẫn biết được N^N chia hết cho A.

Giải thuật:

Ta dùng kết quả sau: một số tự nhiên bất kỳ luôn có thể phân tích thành tích của các thừa số nguyên tố. Hay nói cách khác, số nguyên tố là đơn vị nhỏ nhất khi phân tích một số thành tích các thừa số.
VD:   312=2*3*13;                 123456 = 2⁶*3*643,
Việc chứng mình kết quả này không khó, có thể dùng phản chứng hay diễn giải đều có thể chứng minh được nên mình không chứng minh lại kết quả này.

+Như vậy, số A của chúng ta có thể phân tích thành tích của một số thừa số nguyên tố nào đó:

A=a₁^d1 a ₂^d2 a ₃^d3 _… a _n^dn              với a_1,a_2… là các số nguyên tố.

+Số  N^N muốn chia hết cho A thì trước hết N^N phải chia hết cho các thừa số nguyên tố này. Mà N^N muốn chia hết cho các số nguyên tố này thì N phải chia hết cho các số nguyên tố này.
(Giải thích điều này:
 -Một số A muốn chia hết cho một số B thì A phải có thể phân tích thành tích của B với một số nguyên (A=nB) và ngược lại.
- Giả sử N không chia hết cho 1 trong số các thừa số nguyên tố trên, tạm gọi là số nguyên tố a.  Phân tích N thành tích các thừa số nguyên tố  N=n₁ .n₂. n₃…. n_n thì trong phân tích này sẻ không có thừa số a.  Khi đó  N^N = n₁^N.n₂^N. n₃^N…. n_n^N  thì  chắc chắn rằng cũng không thể có a trong dãy các thừa số nguyên tố này. )

+Như thế, để N có thể chia hết cho các thừa số nguyên tố trên thì N tối thiểu phải bằng tích của các thừa số nguyên tố đó.
+Bây giờ khả năng cao là số N bằng tích của các thừa số nguyên tố chính trên chính là số N nhỏ nhất cần tìm. Nhưng cũng có khả năng là N nhỏ hơn lũy thừa của thừa số nguyên tố nào đó trong phân tích trên, dẫn đến N^N không thể chia hết cho A.
VD: A= 81 = 3⁴ thì nếu như lấy N=3 thì N^N =3³ :không phù hợp. Như thế, lũy thừa của 3 trong N=3³ nhỏ hơn lũy thừa của thừa số 3 trong 81=3⁴.
Để kiểm soát trường hợp này, sau khi tính được N bằng tích của các thừa số nguyên tố, ta cho duyệt kiểm tra một vòng. Kiểm tra  xem N có nhỏ hơn lũy thừa của thừa số nguyên tố nào không, nếu có thì ta kiểm tra N*2 xem lớn hơn chưa , nếu chưa thì kiểm tra N*3,… cho đến khi kiểm tra được N*m lớn hơn lũy thừa của số đó thì thay N=N*m. Ở đây, ta không nhân thêm N với số bị thiếu, mà kiểm tra từ số nhỏ nhất lên.
Ví  dụ như trên: A=81. N=3 nhỏ hơn lũy thừa 4 của thừa số 3 trong phân tích A=3⁴, thì  trong N^N =3³, ta thấy  3³ thiểu 1 lũy thừa và nhân thêm N với 1 số 3 nữa là hoàn toàn sai, khi đó N sẻ bằng 9 nhưng đáp án nhỏ nhất chỉ là 6. Vì khi N được tăng lên, thì lũy thừa cũng tăng vì  là N^N , như thế lũy thừa của thừa số bị thiếu cũng đã được tăng lên rồi.

Mã nguồn:

Ở đây mình dùng 2 mảng 1 chiều để lưu các thừa số nguyên tố và lũy thừa của nó trong phân tích A, và dung biến n để lưu chiều dài 2 mảng này.

#include <stdio.h> void phantichso(int a, int s[], int d[], int& n); void phantichso(int a, int s[], int d[], int& n) {        int i=2;        while (a>1)        {                           if ( (a%i) == 0 )                             {      n++;                                   do                                   {      s[n] = i;                                          d[n]++;                                          a=a/i;                                   } while ((a%i)==0);                            }                i++;        } } int xuly(int s[], int d[],int n); int xuly(int s[], int d[],int n) {        int i,j,kq,t;        kq=1;t=1;j=1;        for(i=1;i<=n;i++)               kq*=s[i];        for(i=1;i<=n;i++)               if (kq<d[i])               {                      for (j=2; t<s[i]; j++)                            t=kq*j;                      kq=t;               }        return kq; }