Tìm N Nhỏ Nhất Sao Cho N^N Chia Hết Cho A - An La (Yên Vũ)

Bài toán: Cho số tự nhiên A. Hãy tìm số tự nhiên N nhỏ nhất sao cho 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

1. Tìm hiểu – Phân tích bài toán

Dễ thấy, với A<=10^9, việc ta tìm kiếm tuần tự giá trị N, cũng như tính bình thường là rất khó khăn. Trường hợp A là 1 số nguyên tố thì N chính bằng A. Với giới hạn đề bài A<=10^9 không cho phép ta tìm kiếm tuần tự như vậy. Ta cần tìm một lời giải khác cải tiến hơn.

chia hết cho A => A là ước của . Việc kiểm tra A là ước của hay không có nhiều cách. Hoặc kiểm tra trực tiếp, hoặc kiểm tra các ước nguyên tố của A và N. Cụ thể:

Giả sử

trong đó a1,a2…ak là các số nguyên tố

Gọi n = a1 x a2… x ak (n>1)

N = qn (với q>0)

=> =

Bài toán đưa về: tìm q nhỏ nhất sao cho (qn)qn chia hết cho A (*)

Chắc chắn sẽ có người thắc mắc khi bài toán con (*) đưa về không khác mấy so với bài toán lớn ban đầu. Tuy nhiên, xem xét kĩ giới hạn của q, ta nhận thấy q nhỏ hơn nhiều so với N:

Ta có N<=10^9, vậy <= 10^9^(10^9) = 10^(9*10^9). có khoảng 9*10^9 chữ số.

q = N/n nên trường hợp q lớn nhất khi n = 2.

Khi đó = = . Với q<=10^5, con số triển khai của <= . Như vậy giới hạn của q là đủ để tìm số N thỏa yêu cầu bài toán.

Vậy thay vì tìm kiếm tuần tự N, ta tìm kiếm tuần tự q

2. Hệ thống lại cách giải và Cài đặt

Từ những phân tích trên, công việc cần làm của chúng ta là:

• Tìm tập các số nguyên tố là ước của A và tính n
• Tìm q nhỏ nhất sao cho chia hết cho A

a. Tìm tập số nguyên tố là ước của A

Nhận xét: Cho một số nguyên dương X bất kì. Nếu p là số nguyên dương nhỏ nhất lớn hơn 1 thỏa X chia hết cho p thì p là số nguyên tố và p là ước nguyên tố nhỏ nhất của X.

Từ nhận xét trên, ta đưa ra cách phân tích A thành các thừa số nguyên tố như sau:

Trong khi A>1 và A không là số nguyên tố

• Tìm a nhỏ nhất sao cho a>1 và A chia hết cho a
• Loại bỏ hết thừa số nguyên tố a trong A để được số A mới. Có thể hiểu là tìm số mũ x của a – tức là tìm x lớn nhất thỏa A chia hết cho , sau đó A= và lặp lại bước trên.

Cứ mỗi lần lặp, ta tìm ước nguyên tố nhỏ nhất của A, loại hết thừa số đó trong A, để tìm ước nguyên tố nhỏ nhất kế tiếp. Cuối cùng dãy a tìm được là các ước số nguyên tố của A. Với điều kiện lặp trên, vòng lặp sẽ thoát nếu A trở thành 1 hoặc A là số nguyên tố. Khi đó ta đã phân tích được A thành các ước nguyên tố <=căn bậc 2 của A. Do đó thay vì kiểm tra A là nguyên tố một cách trực tiếp, ta chỉ cần xét: A là số nguyên tố khi a>căn bậc 2 của A. Mỗi lần lặp tìm giá trị của A, ta tính giá trị n.

Hàm tìm các ước nguyên tố của A và tính n:

int CalN(int A){ int n = 1, a = 2; while (a <= sqrt(A)){ if (A % a == 0){ while (A % a == 0) A /= a; n *= a; } ++a; } return n*A; }

Độ phức tạp của chương trình: sqrt(A)*log(A).

b. Tìm q nhỏ nhất sao cho chia hết cho A

Tìm q: ta tìm kiếm tuần tự giá trị q, cho đến khi nào tìm được q thỏa.

Kiểm tra q thỏa hay không, sử dụng hàm tính số dư khi chia uv cho m.

Nhận xét:

Gọi t=;

Nếu v chẵn, và t*t đồng dư theo mod m

Nếu v lẻ, và t*t*u đồng dư theo mod m

Từ nhận xét trên, ta xây dựng hàm bằng cách tính từ . Độ phức tạp là log(v)

Cài đặt:

long long mod(long long u, long long v, int m) { if (v==1) return u%m; long long t=mod(u,v/2,m); if (v%2==0) return (t*t) % m; return ((u %m)*(t*t %m) %m); } int CalN(int n){ int q=1; while (mod(q*n,q*n,A)!=0) q++; return q*n; }

3. Đánh giá

Ở bước tìm n, độ phức tạp sqrt(A)*log(A).

Ở bước tìm N, tìm kiếm q khoảng 10^5, hàm mod có độ phức tạp log(q*n) = log(N)

Vậy độ phức tạp của chương trình này là sqrt(A)*log(A)+O(100000*log(N)) , chạy tốt với N, A<=10^9

Rate this:

Share this:

• X
• Facebook

Like Loading...

Related