Giúp Past giải bài này với, hu hu...

[ThePast]

Đề là thế này ạh :
Cho trước 2 số M và N nhập từ bàn phím. Tìm số nguyên k sao cho N! chia hết cho M mũ k nhưng không chia hết cho M mũ (k+1).

[bete]

Tui nghĩ như vầy:

Bài này rắc rối ở chỗ N! (giai thừa của N)

Mình phân tích M ra các thừa số nguyên tố. Ví dụ 72 = (2^3)*(3^2)

Kế đến mình phân tích N! ra các thưa số nguyên tố nhưng chỉ xét các thừa số nguyên tố có trong M (ở bước trên) mà thôi . Ví dụ 12! = A*(2^10)*(3^5) (A=(5^2)*7*11)
Lưu ý là ở bước này mình không cần phải tính N!; mà chỉ cần xét các số từ 2 cho đến N mà thôi (2=2^1; 3=3^1; 4=2^2; 5=5^1; 6=(2^1)*(3^1); 7=7^1; 8=2^3; 9=3^2; 10=(2^1)*(5^1); 11=11^1; 12=(2^2)*(3^1) => 12! = (2^10)*(3^5)*(5^2)*7*11))

Bây giờ mình xét các số mũ của các thừa số nguyên tố trong M và N!:
M = 72 = (2^3)*(3^2)
N! = 10! = (2^10)*(3^5)*A (A=(5^2)*7*11)

Số mũ của 2 trong M là 3
Số mũ của 2 trong N! là 10
Mình thấy 10=k1*3 + q1 (xài div & mod: k1=3; q1=1)

Số mũ của 3 trong M là 2
Số mũ của 3 trong N! là 5
Mình thấy 4=k2*2 + q2 (xài div & mod: k2=2; q2=1)

=> mình sẽ chọn k=min(k1,k2)=min(2,3)=2

Thử lại:
M^2 = 72^2 = [(2^3)*(3^2)]^2 = (2^6)*(3^4)
M^3 = 72^2 = [(2^3)*(3^2)]^3 = (2^9)*(3^6)
N! = 10! = (2^10)*(3^5)*A (A=(5^2)*7*11)
=> N! chia hết cho M^2 vì (2^10) chia hết cho (2^6) và (3^5) chia hết cho (3^4)
Nhưng N! KHÔNG chia hết cho M^3 vì (2^10) chia hết cho (2^9) NHƯNG (3^5) KHÔNG chia hết cho (3^6)

(hiểu biết nông cạn, có gì sai sót mong được góp ý, xin cám ơn)

-thân

[cafesua1892]

Tìm số k sao cho n chia hết cho m ^ k. Có nghĩa là n chia hết cho m * m * m *... với k lần. ví dụ nhập m = 2 và n = 16, và 2^4 = 16 như vậy k sẽ = 4.

Xét số 16 đều có thể chia hết cho 2^1 2^2 2^3 2^4 ko chia hết cho 2^5.
16 chia hết cho 4^1 4^2 và ko chia hết cho 4^3.
16 chia hết cho 8^1 và ko chia hết cho 8^2.
16 chia hết cho 16^1 và ko chia hết cho 16^2.
Nhận xét: Những số 2^5 4^3 8^2 16^2 đều là những số có giá trị > 16. Còn nếu trong phạm vi <= 16 thì 16 có thể chia hết được.
Còn những số 16 ko chia được như 3 5 7 9... có bình phương lên cỡ nào cũng ko chia được.
Tóm lại:
bước 1: nhập vào 2 số m, n(DK n chia het cho m va n >= m).
2: nếu n = m kết luận k = 1.
3: gán giá trị cho m1 = m và k:=0.
4: m:= m * m1 đồng thời chạy biến đếm k:=k + 1 CHO ĐẾN KHI (n mod m = 0) and (n mod m * m1 <> 0) or m >= n. Lúc đó ta sẽ có số mũ = k.

Em còn học lớp cấp thấp nên chỉ biết làm như vậy.

[tastsuka]

cách làm của bete chuẩn rồi đáy, còn cafesua1892 bạn hiểu nhầm đề rồi n! chứ ko phải n, hơn nữa cách đó chạy lâu, chỉ sl dc số bé thôi

[cafesua1892]

N! có nghĩa là gì vậy???

[amida]

giai thừa của N T___T

[ThePast]

Híc, cảm ơn anh Bete lắm lắm, nhưng em không chắc là mình làm được, cảm phiền anh viết bài giải luôn được không ạ? T__T

[bete]

Thân gửi ThePast,

Rất tiếc là tui chỉ có thể góp ý mà thôi, bạn thông cảm giùm nghen

Để phân tích 1 số M ra các thừa số nguyên tố thì mình cần có 1 danh sách các số nguyên tố nhỏ hơn M (đúng ra thì nhỏ hơn căn bậc 2 của M)

Để có 1 danh sách các số nguyên tố nhỏ hơn M thi mình có thể xài giải thuật sàng Eratosthenes:

Khởi tạo các phần tử của 1 mảng B về 0
Mình tìm số nhỏ nhứt i chưa bị đánh dấu (B[i] = 0) => đánh dấu các bội số của i (B[k*i] = 1 (k>=2)). Lặp lại với i tăng dần => sẽ được 1 danh sách các số nguyên tố (chỗ nào mà B[j] = 0)
Cụ thể:
Lần lặp lặp thứ 1: B[2] = 0 => 2 là số nguyên tố, đánh dấu 4, 6, 8, 10, ....
Lần lặp lặp thứ 2: B[3] = 0 => 3 là số nguyên tố, đánh dấu 6, 9, 12, 15, ....
Lần lặp lặp thứ 3: B[5] = 0 => 5 là số nguyên tố, đánh dấu 10, 15, 20, 25, ....
(cuối cùng thì có B[2] = B[3] = B[5] = .... = 0 => các số nguyên tố là 2, 3, 5, ...)

Giả sử các số nguyên tố này được chứa trong mảng A (A[1] = 2; A[2] = 3; A[3] = 5, .....) thì mình có thể phân tích M ra các thừa số nguyên tố như sau:

Thử với A[1] (=2): 72 chia hết cho 2 (được 36 dư 0); 36 chia hết cho 2 (được 18 dư 0); 18 chia hết cho 2 (được 9 dư 0) => 72 = (2^3)*....
Thử với A[2] (=3): 9 chia hết cho 3 (được 3 dư 0); 3 chia hết cho 3 (được 1 dư 0) => 72 = (2^3)*(3^2)

Mình cũng có thể đổi giải thuật sàng Eratosthenes ở trên lại 1 chút xíu:

Khởi tạo các phần tử của 1 mảng B về 0
Mình tìm số nhỏ nhứt i chưa bị đánh dấu (B[i] = 0) => đánh dấu i (B[i]=i); và đánh dấu các bội số của i (B[k*i] = i (k>=2)). Lặp lại với i tăng dần => sẽ được 1 danh sách các số nguyên tố (chỗ nào mà B[j] = j)
Cụ thể:
Lần lặp lặp thứ 1: B[2] = 0 => 2 là số nguyên tố, đánh dấu 2, 4, 6, 8, 10, ....
Lần lặp lặp thứ 2: B[3] = 0 => 3 là số nguyên tố, đánh dấu 3, 6, 9, 12, ....
Lần lặp lặp thứ 3: B[5] = 0 => 5 là số nguyên tố, đánh dấu 5, 10, 15, 20, ....
(cuối cùng thì có B[2]=2; B[3]=3; B[5]=5; .... => 2, 3, 5, ... là các số nguyên tố vì B[j] = j;
B[4] = 2; B[6]=3; B[8]=2 => 4, 6, 8, ..... không là các số nguyên tố vì B[j] khác j)

Sau đó để phân tích 72 thành các thừa số nguyên tố thì mình làm như sau:

B[72] = 3 => 72 chia hết cho 3 (được 24 dư 0)
B[24] = 3 => 24 chia hết cho 3 (được 8 dư 0)
B[8] = 2 => 8 chia hết cho 2 (được 4 dư 0)
B[4] = 2 => 4 chia hết cho 2 (được 2 dư 0)
B[2] = 2 => 2 chia hết cho 2 (được 1 dư 0)
=> 72 = (2^3)*(3^2)

(hiểu biết nông cạn, có gì sai sót mong được góp ý, xin cám ơn)

-thân

[ThePast]

Da, du` sao cung~ cam on anh rat nhieu !

[thuonghcm]

theo tui thì:
n:=giaithua(n); {tự thiết kế}
function luythua(a,p):longint;{tự thiết kế}
{main}
for k:=0 to maxint-1 do
if (n mod luythua(m,k)=0)and(n mod luythua(m,k+1)<>0)then
begin write(k);break end;
{lam kiểu này thì mình sướng mà máy thì cưc, voi lại số lớn quá nó chạy...khônng nổi,,hihihihihi}