CHIA HẾT VỚI SỐ THỰC ( bài 1 - đề án )

• Bài toán đặt ra:

    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

• Ý tưởng ban đầu:

     Đầu tiên vào ai trong chúng ta cũng sẽ nghĩ ngay đến phép mod ( nghĩa là k mod a =0 thoả):

è trong C/C++ thì chỉ dùng được với số nguyên tối đa 2³²  nên cách trên với bài toán này đành phá sản.

     Vậy để thoả giới hạn của số trên chỉ có cách dùng kiểu Double nhưng kiểu này lại là số thực không có phép mod (%) nên bạn phải làm gì đây?

è bài toán trên trở thành việc giải quyết làm sao biết 1 số thực có chia hết cho 1 số thực hay không?

     Ở đây mình đưa ra 1 cách xử lý đơn giản và thủ công như sau:

-         Gọi k là số đưa vào kiểm tra , A theo đề

-         (k*k) chia hết cho A ó ceil(k*k*...*k /a)*a=(k*k)

Nghĩa là: làm tròn thương số (k*k...*k/a) rồi *a nếu không chia hết thì thương số sẽ bị làm tròn lên hoặc xuống ngay dẫn đến việc *a sẽ không bằng lại (k*k*....k)

     Việc thứ 2 bạn cần đó là hàm tính k*k*…k = K^k là hàm pow trong thư viện


Với cách xử lí này tuy chạy hơi lâu nhưng sẽ đơn giản về mặt suy luận và điều quan trọng mình muốn chia sẽ ở đây là cách chia hết với 1 số thực còn về thuật toán để bài này chạy với hiệu suất cao hơn sẽ được đăng lên trong thời gian sớm nhất có thể. 

•  Bài giải tham khảo:

#include

#include

#include

void main()

{

    double i,n,k;

    printf(" nhap vao so a= ");

    scanf("%lf",&n);

    for (i=2 ; i<=n ; i++)

         {

             k= pow(i,i);

         if (ceil(k/n)*n==k)

             {

                 printf("%0.0lf \n",i);

                 break;

             }

         }

   

}