TIN TỨC CẬP NHẬT

Chuyên đề về số học

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Chuyên đề về số học

Bài gửi by pkt_zz on 13/6/2010, 2:22 am

Nguồn: [You must be registered and logged in to see this link.]
Bài 1 : Amount of Degrees

Một số A gọi là có bậc K đối với cơ số B nếu như :

· A = Bx1 + Bx2 + … + Bxk

(trong đó x1 ¹ x2 ¹ x3 … ¹ xk )

Ví dụ :

· 17 có bậc 2 đối với cơ số 2 vì 17 = 24 + 20 .

· 151 có bậc 3 đối với cơ số 5 vì 151 = 53 + 52 + 50.

Yêu cầu : Cho trước 1 đoạn [X,Y] . Hãy xác định xem trong đoạn này có bao nhiêu số có bậc K đối với cơ số B.

Giới hạn : + 1 £ X £ Y £ 109.

+ 1 £ K £ 20, 2 £ B £ 9.

+ Bộ nhớ : 200KB.

+ Time limit : 1 s.

Input

X Y K B

Output

Gồm 1 số duy nhất là kết quả tìm được .

Ví dụ

Input

15 20 2 2

Output

3

( Giải thích : Đó là các số 17 = 24 + 20 .

18 = 24 + 21.

20 = 24 + 22. )

Thuật giải :

Ta sẽ đưa bài toán này về một bài toán nhỏ hơn đó là cho biết trong đoạn [1,A] có bao nhiêu số có bậc K đối với cơ số B.

Với mỗi giá trị A ta đều xác định được Bn sao cho Bn+1 > A . Áp dụng tính chất: Bn > Bn-1 + Bn-2 + … B0 ® A > Bn-1 + Bn-2 + … B0.

® Tổng bất kỳ của 1 tổ hợp K phần tử của (n-1) phần tử này cũng đều < A ( tức là : A > Bx1 + Bx2 + …+ Bxi +… + Bxk ( với mọi xi £ n–1 ) ).

® Như vậy ta đã giải quyết xong vấn đề với các số mà không chứa Bn, nếu như không chứa Bn thì số lượng số thoả mãn sẽ = Tổ hợp chập K của (n-1) . Ta sẽ tiếp tục giải quyết vấn đề với các số mà có dạng = Bn + Bx2+…+Bxk.Dễ thấy vấn đề ở đây lại quay về là tìm số lượng các số có bậc (K-1) đối với cơ số B trong đoạn [1,A-Bn] và không chứa Bn, vậy thì ở đây ta chỉ cần xác định lại n mà thôi, n(mới) £ n (cũ) – 1.

Như vậy bài toán đã được giải quyết. Nói tóm lại đây là một bài khá đặc trưng cho QHĐ = Đệ quy với công thức truy hồi đơn giản :

Cal(A,K,B) = Tổ hợp chập K của (N-1) + Cal(A-Bn,K-1,B).

Bài 2 : Nikifor – 2

Nikifor có một số X nhưng đó không phải là con số mà anh ta cần. Anh ta muốn đổi con số X này lấy con số Y mà anh ta thích. Để đổi được con số Y này anh ta phải chọn ra một cơ số K sao cho ta có thể đạt được số Y bằng cách xoá đi một vài chữ số của số X trong biểu diễn của hệ cơ số K .

Ví dụ : X = 19 , Y = 4 , K = 3.

Biểu diễn của X trong hệ cơ số 3 = 201

Biểu diễn của Y trong hệ cơ số 3 = 21

Vậy ta có thể đạt được số Y bằng cách xoá đi số 0 trong biểu diễn của số X .

Yêu cầu : Hãy tìm cơ số K nhỏ nhất có thể được .

Giới hạn : + 1 £ X , Y £ 106.

+ Time limit 1 s , bộ nhớ 200 KB.

Input

X Y

Output

Nếu tồn tại K thì ghi ra K nhỏ nhất , nếu không tồn tại thì ghi ra “No Solution”.

( Lưu ý số K có thể ³ 10 , không nhất thiết là nhỏ hơn 10 )

Ví dụs

Input

19 4

Output

2

Thuật giải :

Ta duyệt tất cả các số K từ 2 -> Y . Tuy nhiên điều muốn nói ở đây là làm cách nào để có thể kiểm tra xem với một cơ số K có đáp ứng được yêu cầu hay không một cách nhanh nhất ! Nếu như làm bình thường thì ta sẽ xây dựng được biểu diễn của X, của Y .Nếu xâu con chung dài nhất của X và Y = Y -> Đáp ứng yêu cầu ! Hoặc một cách cải tiến khác cũng đưa về xâu dựa trên nhận xét : xâu con chung dài nhất của X , Y = Y tương đương với các phần tử của Y xuất hiện đúng theo thứ tự này trong xâu X , tức là xâu con chung dài nhất Y = Xi1Xi2…Xik thì i1 < i2 < … < ik . -> Ta có thể sủ dụng thuật toán được mô tả sau đây : ( Cải tiến 1 )
Code:

Ok := True ;

While Y <> Æ do Begin

While X[1] <> Y[1] do Begin

Delete(X,1,1) ;

If X = Æ then Begin

Ok := False ; Exit ;

End ;

End ;

Delete(X,1,1) ; Delete(Y,1,1) ;

End ;
Tuy có cải tiến như vậy nhưng về cơ bản cấp độ của thuật toán là khá cao ( + thời gian tạo xâu ) và không thể chấp nhận được trong thời gian giới hạn là 1 s. Vì vậy ta cần có một thuật toán kiểm tra tốt hơn là đưa về xâu ! Ý tưởng của thuật toán là thay vì đổi ra xâu ta sử dụng phép div , nếu như trong hệ cơ số K ta sử dụng phép div K thì cũng giống như ta sử dụng phép shr trong hệ nhị phân ! Nó sẽ dịch chuyển số X về bên phải một chữ số ! Ta áp dụng cải tiến 1 trong trường hợp này là so sánh chữ số cuối cùng chứ không phải chữ số đầu tiên nữa ! Và chữ số cuối cùng của X = X mod K , chữ số cuối cùng của Y = Y mod K . Thủ tục Delete sẽ được thay bằng X = X div K . Như vậy thuật toán với 2 cải tiến này sẽ giảm được rất nhiều thời gian lãng phí do phải tạo xâu, sinh luỹ thừa ! Về mặt thời gian là chạy khá tốt !

Ngoài ra còn một thuật toán có cấp độ O( (logY)3 ) mà ta không đề cập tới ở đây mà sẽ nhắc tới ở một chương khác. Mặc dù vậy với X , Y £ 106 thì ta có thể yên tâm là thuật toán này chạy chậm gấp 2,5 lần thuật toán duyệt với 2 cải tiến ở trên !

Bài 3 : Central Heating

Trong một trường đại học có một hệ thống N lò sưởi được đánh số từ 1-> N ! N lò sưởi này được điều khiển bởi N kỹ sư được đánh số từ 1 -> N ! Mỗi lò sưởi chỉ có 1 công tắc là tắt/bật lò sưởi mà thôi ! Tuy nhiên oái oăm thay là mỗi kỹ sư lại điều khiển 1 vài lò sưởi chứ không phải chỉ 1 lò sưởi! Và khi họ đi làm thì nếu như được chỉ định là trực ở lò sưởi thì họ sẽ đi thay đổi công tắc ở tất cả các lò sưởi mà họ điều khiển, nếu đang bật -> tắt và tắt -> bật. Kỹ sư thứ i sẽ tới vào trường vào lúc i giờ. Ban giám hiệu trường muốn đảm bảo sức khoẻ cho sinh viên nên phải phân công kỹ sư trực sao cho đến giờ thứ N+1 thì tất cả lò sưởi đều đang ở trạng thái bật !
Yêu cầu : Bạn được thuê giúp đỡ Ban Giám Hiệu của trường ! Hãy chỉ ra xem những kỹ sư phải được chỉ định là trực để đáp ứng yêu cầu của ban giám hiệu là những kỹ sư nào ! Nếu có nhiều phương án thì cho biết phương án mà số kỹ sư bị chỉ định là ít nhất.

Giới hạn : + 1 £ N £ 200.

+ Time limit 2 s , bộ nhớ 200 KB

Input

- Dòng 1 ghi số nguyên N

- N dòng tiếp theo có cấu trúc gồm 1 số Li ( số lò sưởi mà kỹ sư thứ i điều khiển ) và tiếp sau đó là Li số là chỉ số của các lò sưởI mà kỹ sư i điều khiển )

Output

- Nếu không có phương án thì ghi ra 1 dòng duy nhất : “No solution”. Ngược lại :

- Dòng 1 ghi số K là số kỹ sư tối thiểu được chỉ định

- Dòng 2 gồm K số là chỉ số của các kỹ sư được chỉ định .

Ví dụ :

Input

4

2 1 2

3 2 3 4

1 2

1 4

Output

3

1 2 3

Thuật giải :

Đây là một bài giải hệ phương trình nhị phân khá đơn giản. Ta có thể sử dụng khử Gauss để giải hệ . Nghiệm có số phần tử bằng = 1 ít nhất chính là phương án sử dụng ít kỹ sư nhất ! Cấp độ của khử Gauss vào khoảng O(N3) là chấp nhận được.

Bài 4 : Simple Calculations

Có một dãy số thực gồm N+2 phần tử A0 , A1, … , An+1. Dãy này có tính chất đặc biệt là A[i] = ( A[i-1] + A[i+1] ) / 2 – C[i] với i = 1,2,3…,n.

Yêu cầu : Cho dãy C và A0 , An+1. Hãy tính A1.

Giới hạn : + 3 £ N £ 3000.

+ -1000 £ Ai , Ci £ 1000.

+ Time limit 1 s , bộ nhớ 200 KB .

Input

N

A0 An+1

C1

C2



Cn

Output

A1 ( Ghi chính xác đến 2 chữ số sau dấu phẩy ) .

Ví dụ :

Input

1

50.50 25.50

10.15

Output

27.85

Thuật giải :

Ta có A(1) = ( A(0) + A(2) ) / 2 – C(1)

A(2) = ( A(1) + A(3) ) / 2 – C(2)

….

A(n) = ( A(n-1) + A(n+1) ) / 2 – C(n)

® A(1) + A(2) + … A(n) = ( A(0) + A(n+1) + A(1) + A(n) ) / 2 + A(2) + A(3) + …+A(n-1) – ( C(1) + C(2) + C(3) +…+C(n) ) .

Û A(1) + A(n) = A(0) + A(n+1) – 2*( C(1) + C(2) + C(3) +…+C(n) ) .

Tương tự ta có : A(1) + A(n-1) = A(0) + A(n) – 2*( C(1) + C(2) + C(3) +…+C(n-1) ) .

………..

A(1) + A(1) = A(0) + A(2) – 2* C(1) .

® A(1) * (n+1) = A(0) * n + A(n+1) – 2 *( C(1) + C(2) + C(3) +…+C(n) )

- 2*( C(1) + C(2) + C(3) +…+C(n-1) ) – …- 2*C(1).

è Ta tính được A(1). Cấp độ thuật toán O(n). Cũng với phương pháp này ta có thể tính được tất cả các phần tử của dãy A cũng chỉ với cấp độ O(n).

Bài 5 : Nikifor – 3

Nikifor có một số tự nhiên N. Anh ta là một người rất yêu thích con số 7 ( giống mình ). Bởi vậy con số của anh ta phải là một con số chia hết cho 7. Nhưng rất tiếc con số N của anh ta lại chưa phải là bội của 7 . Bây giờ anh ta muốn đổi vị trí của các chữ số của số N sao cho tạo được một số mới mà số này chia hết cho 7. Vì Nikifor là một người rất đặc biệt nên con số N của anh ta cũng rất đặc biệt. Số N này luôn có đủ 4 chữ số 1 , 2 , 3 4 trong biểu diễn thập phân của mình ! Hơn nữa nếu số N này đã là bội của 7 rồi thì anh ta vẫn muốn biến đổi để ra được 1 số mới khác cũng chia hết cho 7.
Yêu cầu : Hãy giúp Nikifor đổi vị trí của các chữ số trong số N sao cho được số mới chia hết cho 7.

Giới hạn : + số N này có không quá 1000 chữ số và có ít nhất 4 chữ số .

+ Time limit : 1s , bộ nhớ 200KB.

Input

- Dòng 1 : 1 số X là số bộ test. ( 1 £ X £ 10000 ).

- X dòng tiếp theo mỗi dòng ghi 1 số N.

Output

N dòng ghi ra kết quả của từng test , nếu test nào vô nghiệm thì ghi ra “No solution” ngược lại ghi ra số N sau khi biến đổi .

Ví dụ :

Input

2

10234

531234

Output

32410

353241

Thuật giải :

Nhận thấy số N luôn có đủ 4 chữ số 1,2,3,4 . Với 4 số này ta có thể tạo thành bất kỳ số dư nào trong các số dư từ 0->6 :

Ví dụ : 1234 mod 7 = 2 , 3241 mod 7 = 0 …

Như vậy ta có một cách làm rất hay cho bài này đó là : đặt tuỳ ý các chữ số # 0 vào đầu sao cho còn dư lại 4 chữ số 1 , 2 , 3 , 4 . Với 4 chữ số này ta sẽ đặt vào tiếp theo , sau cùng mới đặt các chữ số 0. 4 chữ số 1,2,3,4 cuối ta sẽ duyệt hoán vị của nó xem hoán vị nào của nó thì số N tạo được sẽ chia hết cho 7. Vì với mỗi số dư R đều có ít nhất 2 hoán vị nên dù N cũng có dạng như trên thì cũng có ít nhất 1 số khác cũng cùng dạng này nữa -> Bài toán không bao giờ vô nghiệm ! Vì 4! = 24 -> Chạy rất nhanh !

Bài 6 : Pinocchio

Cha của Pinocchio muốn làm lại cho Pinocchio một cái mũi mới . Ông có N thanh gỗ , mỗi thanh gỗ có độ dài Ai. Là người yêu thích toán học ông ta đưa ra một giải thuật sau để lấy ra thanh gỗ có độ dài cần thiết :

· Nếu còn lại 1 thanh gỗ thì ông ta sẽ lấy thanh gỗ này làm mũi cho Pinocchio.

· Nếu còn >= 2 thanh gỗ thì ông ta sẽ làm như sau :

Ø Chọn ra 2 thanh gỗ i , j sao cho Ai và Aj có độ dài nhỏ nhất trong số N thanh.

Ø Nếu Ai = Aj thì vứt bỏ một thanh đi, lại quay về bước 1

Ø Nếu Ai < Aj thì ta sẽ cắt thanh Aj đi một đoạn = Ai ( tức là Aj = Aj – Ai).

Quay lại bước 1.

Yêu cầu : Hãy tính xem độ dài mà thanh gỗ ông ta nhận được sẽ là bao nhiêu.

Giới hạn : + 1 £ N £ 100000.

+ 1 £ Ai £ 109.

+ Time limit 1s , bộ nhớ 200 KB.

Input

N

A1

A2



An

Output

Gồm 1 số duy nhất X là độ dài thanh gỗ đạt được.

Ví dụ:

Input

3

2

3

4

Output

1

Thuật giải :

Dễ dàng CM được đó chính là ước chung lớn nhất của N số . Ta có thể dùng thuật toán Oclit. Cấp độ tính toán của bài này là O(n).

Bài 7 : Button

Trong đại hội thể thao Olympic năm 3000, người ta quyết định đưa môn bốc sỏi vào thi đấu. Trận đấu sẽ gồm 2 người thi đấu và có K viên sỏi , đến lượt người nào chơi thì được bốc không quá L viên ! Ai đến lượt mình mà không còn gì để bốc nữa thì sẽ thua ! Đấu thủ thứ nhất được quyền chọn xem số K sẽ là bao nhiêu ! Còn đấu thủ thứ 2 được quyền chọn xem số L sẽ là bao nhiêu ! Giả sử đã biết được người thứ nhất chọn số K là bao nhiêu ,bạn hãy giúp người thứ 2 chọn ra số L nhỏ nhất sao cho người thứ 2 chắc chắn giành phần thắng và số L > 1.

Giới hạn : + 2 < K < 109.

+ Time limit 1s , bộ nhớ 200KB.

Input

K

Output

L

Ví dụ :

Input

6

Output

2

Thuật giải :

Đây là một bài toán trò chơi cổ điển, 1 số L để người 2 chắc chắn thắng thì K phải chia hết cho (L+1). Vậy thì đó sẽ là ước nhỏ nhất của K ( mà > 2 ) – 1. Khi tìm ước cần chú ý đến 1 số trường hợp đặc biệt là 14 chẳng hạn , kết quả trả ra sẽ là 6 nhưng mà do không cẩn thận ( có thể là do tìm ước = hàm kiểm tra nguyên tố lấy Sqrt trong khi Sqrt(14) = 3.7416 nên sẽ dẫn tới sai xót ! ).

Bài 8 : Combinations

Yêu cầu : Rất đơn giản ! Hãy tính xem C có bao nhiêu ước nguyên tố với C được tính = CT :

C = N! / ( ((N-M)!) * (M!) )

Tất nhiên ở đây N và M là 2 số cho trước .

Giới hạn : + 1 £ M £ N £ 60000.

+ Time limit 1s , Bộ nhớ 200KB.

Input

N M

Output

Gồm 1 số duy nhất là số ước của C.

Ví dụ :

Input

7 3

Output

2

( Giải thích : C = 35 = 5*7 ).

Thuật giải :

Ta phân tích N! , M! thành tích của các số nguyên tố .

® N! = 2x1 * 3x2 * …

M! = 2y1 * 3y2 * …

(N-M)!= 2z1 * 3z2*…

® C = 2x1-y1-z1 * 3x2-y2-z2 * ….

Ta chỉ việc đếm thôi , với xi-yi-zi > 0 thì ta tăng số phần tử tìm thấy lên 1. Thuật toán hoàn toàn rất đơn giản. Tuy nhiên để thuật toán chạy nhanh ta nên áp dụng công thức Lagrăng như sau :

Số mũ của số nguyên tố P trong N! = [N/P] + [N/(P2)] + … [N/(Pk)].

với [q] = phần nguyên của số q.

Bài 9 : Fibonacci sequence

Có một dãy số dài vô hạn thoả mãn tính chất Fibonacci .

Đó là : F[i] = F[i-1] + F[i-2]. ( Với mọi i thuộc Z ).

Yêu cầu : Cho biết F[i] và F[j] . Hãy tính F[n].

Giới hạn : + -1000 £ i ¹ j , n £ 1000.

+ -MaxLongInt £ F[i] , F[j] , F[n] £ MaxLongInt.

+ Time limit 1s , bộ nhớ 200KB.

Input

i F[i] j F[j] n

Output

F[n]

Ví dụ :

Input

3 5 –1 4 5

Output

12

Thuật giải :

Đối với bài này có 2 cách làm . Giả sử i < j .

Cách 1 : Duyệt nhị phân giá trị của F[i+1] . Với mỗi giá trị của F[i+1] ta sẽ kiểm tra xem số F[j] có đúng với đề bài không ! Nếu đúng thì dừng lại và sinh F[n]. Biết F[i] , F[i+1] thì rõ ràng ta có thể tính được toàn bộ phần tử thuộc dãy.

Cách 2 : Dựa vào CT :

F[i+1] = 1 * F[i-1] + 1 * F[i] ;

F[i+2] = 1 * F[i-1] + 2 * F[i] ;

F[i+3] = 2 * F[i-1] + 3 * F[i] ;

F[i+4] = 3 * F[i-1] + 5 * F[i] ;

F[i+5] = 5 * F[i-1] + 8 * F[i] ;



F[j] = x * F[i-1] + y * F[i].

Nếu để ý ta sẽ thấy hệ số của F[i-1] , F[i] chính là một dãy Fibonacci . Vậy thì ở đây công việc còn lại sẽ rất đơn giản. Ta chỉ việc tính xem x , y là bao nhiêu nữa là xong ! Chú ý một chút nho nhỏ nếu dùng Cách 2 đó là x, y có thể là rất lớn nên khai báo kiểu Extended là tốt nhất.

Bài 10 : SKBJunk 307

SKBJunk 307 là rô bốt đời mới nhất của trung tâm nghiên cứu vũ trụ VNSC ( Viet Nam Space Center ) . Nó được trang bị khả năng tính toán siêu việt. An là một người thích nổi tiếng, để cho mọi người thấy SKBJunk 307 tính toán còn chậm hơn cả một máy tính thông thường, anh ta đã thách đấu với nó. Nội dung của cuộc thi là tính xem 1N + 2N + 3N + 4N có bao nhiêu chữ số 0 ở cuối cùng. An biết chắc là sẽ thua nên đã thuê bạn giúp anh ta.

Yêu cầu : Hãy lập trình tính xem 1N + 2N + 3N + 4N có bao nhiêu chữ số 0 ở cuối cùng.

Giới hạn : + 1 £ N £ 300000.

+ Time limit 1 s , bộ nhớ 200KB.

Input

N

Output

Gồm 1 số X duy nhất là kết quả tính được.

Ví dụ:

Input

1

Output

1

Thuật giải :

Dễ thấy kết quả trả ra luôn chỉ có thể là 1 trong 3 số : 0 , 1 , 2.

Kết quả của bài toán này đã được CM bởi Euler đó là :

N) = N mod 2000).

Bởi vậy thay vì tính số mũ từ 1-> N ta chỉ phải tính số mũ từ 1-> N mod 2000 mà thôi. Tuy nhiên trong thực tế ( với N <= 300000) thì ta chỉ cần tính số mũ từ 1 -> N mod 100 mà thôi.

pkt_zz
THƯỢNG TƯỚNG V
THƯỢNG TƯỚNG V

Tổng số bài gửi : 1029
Join date : 15/12/2009
Age : 25
Đến từ : MẠC XÁ-QUANG PHỤC

Xem lý lịch thành viên http://lop12a5thpttk-0609.forumotion.net

Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết