Tìm số N thỏa điều kiện cho trướ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^N chia hết cho A. Viết chương trình tìm số đó và xuất ra màn hình. Trong đó A có giá trị: 1<=A<=10^9

         Nhận xét: Với miền giá trị của A từ 1 đến  10^9  thì việc tính  N^N  có khả năng sẽ dẫn đến một giá trị vô cùng lớn, và khả năng bị lỗi cũng sẽ tăng cao. Đặc biệt, nếu như gái trị A nhập vào ban đầu là một số nguyên tố thì N lại chính là bằng A. Việc tìm kiếm tuần tự từ 1 đến A là không tối ưu.

         Bước 1:Điều kiện để một số nguyên bất kì X chia hết cho A
X chia hết cho A <=> X và A có cùng lượng thừa số nguyên tố và bằng nhau từng đôi một.
 
         Bước 2: Phát hiện:
Đặt N = ∏i=1kpi với p_i là thừa số nguyên tố thứ i  là số nguyên tố thứ i, k là lượng thừa số nguyên tố.

            + Xét A =  ∏i=1kpibi, Nếu N^N chia hết cho A thì đáp án phải là bội của N.

Vậy: N^N thực chất chỉ là nhân N cho các số mũ của những thừa số nguyên tố.

          Bước 3: Lập thuật toán.

           

            + Đầu tiên, phân tích A = ∏i=1kpibi

            + Ta đặt: N = ∏i=1kpi. Nếu N ≥ 29, in N và thoát.

+ Tìm số mũ p₁, p_­­2. 2 số này ta đặt là a, b => N = p₁^a.p₂^b; bài toán trở về việc tìm 2 số a, b sao cho a.N ≥ b₁, b.N ≥ b₂, a≥ 1, b ≥ 1 và tích a.b nhỏ nhất.