Bài 1 Sự giới hạn của Vật Lý và lối thoát Toán học

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ới đề trên ta  có thể dùng thuật toán đơn giản: là cho vòng lặp cho N chạy từ 1 đến A và tính N^N chia hết cho A và xuất N như đề bài với thuận toán trên ta có đoạn mã sau:

#include <iostream>

#include <math.h>

using namespace std;

void main ()

{

     int in,ia;//in la N, ia la A

     cout<<"nhap so nguyen A (1<=A<=10^9)"<<endl;

     cin>>ia;

     for(in=0;in<=ia;in++)//cho N chay tu 1 den A

     {

           if((int)pow(float(in),(float)in)%ia==0)// tinh N ngu N tim se chia het cho A khong

                break;

           if(in==ia)// bang A tinh dung vong lap

                break;

     }

     cout<<"so nguyen N phu hop voi dieu kien de bai la "<<in<<endl;//xuat ra ket qua

     system("pause");

}

Ta có thể thấy được hạn chế của thuật toán này phụ thuộc vào quá nhiều khả năng lưu trữ của máy tính. Nên với số quá lớn thì ta sẽ không tính N^N để không sử dụng quá nhiều vào khả nẳng lưu trữ của máy tính. Vậy phải tìm một thuật toán tìm được N mà không cần tính N^N. Có thể thấy điểm quan trọng của bài toán là phép chia hết. Vậy ta phải tìm hiểu rõ tính chất chia hết.Theo nguồn tìm kiếm trên mạng, ta có định lý cơ bản của số học: “Định lý cơ bản của số học (hay định lý về sự phân tích duy nhất ra các thừa số nguyên tố) phát biểu như sau: Mọi số tự nhiên lớn hơn 1 có thể viết một cách duy nhất (không kể sự sai khác về thứ tự các thừa số) thành tích các thừa số nguyên tố”...

“Một cách tổng quát: Mọi số tự nhiên n lớn hơn 1, có thể viết duy nhất dưới dạng:

trong đó  là các số nguyên tố. Vế phải của đẳng thức này được gọi là dạng phân tích tiêu chuẩn của n”. nguồn

vậy ta có thể thấy số nguyên A có thể phân tích thành tích các thừa số nguyên tố. Vậy để N^N chia hết cho A phải thỏa 2 điệu kiện:

-khi phân tích ra phải có các thừa số nguyên tố giống A.

- phải lớn hơn A tức số mũ của các thừa số nguyên lớn hơn của A.

Với đề bài cho  1 ≤ A ≤ 10⁹ thì  khi phân tích thừa số nguyên tố với mũ 1 thì ta có 3 trường hợp:

Trường hợp chỉ có 1 số nguyên tố , với các số 2,3,5,7 thì ta phải tìm số mũ để nó thỏa mãn điều kiện để N^N lớn hơn A. Nếu từ 11,13,… thì N sẽ bằng chính nó vì 11¹¹>10⁹.

Trường hợp 2 số nguyên tố trở lên, thì ta thấy chỉ có 2 và 3 phải xét độ lớn N^N còn các trường hợp còn lại thì nó sẽ chính bằng N vì với 2 và 5 tức 10¹⁰>10⁹.

Vậy làm sao tính độ lớn N^N khi ta đã chủ động tránh nó.

Đối với chỉ có 1 thừa số nguyên tố 2, 3, 5, 7 thì ta có: do cơ số của A và N bằng nhau và bằng thừa số nguyên tố tìm được nên để giảm độ lớn của phép tính thì ta chỉ so sánh mũ của A và N

Với x.N^x>a

-          x là số mũ cần tìm

-          N là thừa số nguyên tố

-          a là số mũ của nguyên A

vậy công việc của chỉ cần tìm x.

Đối với trường hợp thừa số nguyên tố 2 và 3 thì với mũ 1 tức N=6 thì sẽ giới hạn A < 6⁶. Vậy có cần tính N^N không hay tính số mũ như trên. Nếu chú ý thì ta sẽ thấy giới hạn của A ≤ 10⁹ vậy ta phải tìm số mũ lớn 9 như nhỏ nhất. Nếu phải tính mũ thông thường thì rất phức tạp làm cho thuật toán dài thêm. Vậy ta phải tìm N sao cho lớn hơn 9 và nhỏ nhất. vậy từ 2 và 3 số N chỉ có thể là 12. Với 2².3 < 2.3³ . vậy đối với A < 6⁶ thì N=12.

Theo các suy luân trên ta có thuật toán:

-          Phân tích A thành thừa số nguyên tố có mũ là 1

-          Sẽ các trường hợp đặc biệt: 2, 3 ,5 ,7; 2 và 3

Ta có đoạn mã mô tả thuật toán trên:



#include <iostream>

#include <math.h>

using namespace std;

void timsonguyento(unsigned int& it,unsigned int in)

//ham kiem tra so nguyen to

{

     unsigned int im;

     im=2;

      it=1;

           while(im<in)

           {

                if(in%im==0)

                {

                     it=0;

                     break;

                }

                     im++;

              }

}

void songuyento (unsigned int in,unsigned int& ib)// ham phan tich 1 so thanh tich cua cac so nguyen to

{  

     unsigned int im,it;

     im=1;

     while(im<=in)

     {

           if (in%im==0)

                timsonguyento(it,im);

           if(it==1)

                if(in%im==0)

                           ib*=im;

           im++;

     }

}

void motsonguyento (unsigned int ia,unsigned int& in)

//ham kiem tra cac truong hop 1 so nguyen to

{

     int ib,ic;

     for(ib=1;ia>in;ib++)

     {

           ia=ia/in;

     }

     for(ic=0;1!=0;ic++)

     {

           if((ic*pow((float)in,(float)ic))>ib)

           {

                in=pow((float)in,(float)ic);

                break;

           }

     }

}

void main ()

{

     unsigned int ia,in=1;

     do

     {

           cout<<"nhap so nguyen A (1<=A<=10^9) "<<endl;

           cin>>ia;

     } while(ia<=0);

     songuyento(ia,in);

     if(in==2||in==3||in==5||in==7)

           motsonguyento(ia,in);

     if(in==6)

//ham kiem tra truong hop 2 va 3

     {

           if(ia<pow(6.0,6))

                in=6;

           else

                in=12;

     }

     cout<<"N nho nhat de cho N ngu N chia het cho A la "<<in<<endl;

     system("pause");

}