24/11/2011

Bài toán số học N mũ N chia hết cho A bất kỳ

Bài 1: Cho số tự nhiên A. Tìm số tự nhiên N nhỏ nhất sao cho NN 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ị từ 1 đến 109 .
Ví dụ:  Nhập A=8, xuất ra N=4.
           Nhập A=13, xuất ra N=13.
     
Hướng giải quyết:

Vì NN chia hết cho A nên NN chia hết cho tất cả các ước nguyên tố của A. Suy ra N chia hết cho tất cả các ước nguyên tố của A. 
Nếu phân tích A ra thừa số nguyên tố A = p[1]e[1] .p[2]e[2].p[3]e[3].p[4]e[4]...........p[k]e[k]  thì N có dạng N = p[1]t[1] .p[2]t[2].p[3]t[3].p[4]t[4]...........p[k]t[k] .
Suy ra:
NN = p[1]t[1].N .p[2]t[2].N.p[3]t[3].N.p[4]t[4].N...........p[k]t[k].N chia hết cho A khi và chỉ khi với với i∈(1,k), t[i].N ≥ e[i].