SỐ HỌC

Khôi Hoàng đang dạy bé Nhã Phương toán học. Khôi Hoàng ra đề cho bé Phương như sau :

"Cho em hai số nguyên 𝑝 và 𝑞, hãy tìm một số nguyên 𝑛 nhỏ nhất sao cho khi lấy chữ số đầu tiên đưa xuống thành chữ số cuối cùng thì sẽ được số mới bằng 𝑝/𝑞 lần số cũ"

Bé Phương không muốn mình cảm thấy thua thiệt nên đã nhờ anh Đinh Khôi giải giúp. Anh Khôi vì muốn lấy lệ với gái nên đã bảo :"Ừ, em về đi, mai anh sẽ đưa em lời giải". Nhưng thực tế anh Khôi đã bí rồi. Bạn hãy cứu anh ấy nào.

Dữ liệu: Vào từ file văn bản NUMBER.INP gồm hai số 𝑝𝑝 và 𝑞 (1 ≤ 𝑝, 𝑞 ≤ 2^31-1).

Kết quả: Ghi ra file văn bản BEAUTIFUL.OUT một số nguyên 𝑛 (1 ≤ 𝑛 ≤ 2×10⁹) đồng thời thỏa mãn điều kiện bài toán. Nếu không tồn tại 𝑛 thì in ra -1.

Ví dụ:

NUMBER.INP	NUMBER.OUT
1 4	102564

Giải thích: Nếu ta đưa số 1 ra sau cùng, ta được số 25641 và 25641 = 102564 × ¼.

Test - đề (word)

Dãy số Fibonacci

Nhật Khôi rất thích nghiên cứu về toán. Bài toán hiện tại mà cậu ấy đang nghiên cứu là dãy Fibonacci với quy luật như sau:

·         𝑓₀ = 0, 𝑓₁ = 𝑥;

·         𝑓_𝑛 = 𝑓_𝑛−1 + 𝑓_𝑛−2 (∀ 𝑛 > 1).

Nhật Khôi rất thích thú khi đã tính được tới số Fibonacci thứ 𝑛. Sau đó cậu quyết định đi ngủ. Trong lúc ngủ, không biết rằng Nga Hằng Nguyễn đã chui từ đâu ra và phá nát mất 2 số 𝑓₀ và 𝑓₁ của Nhật Khôi. Nhật Khôi ngồi khóc một mình trong 4 bức tường vì cậu ấy không thể tìm ra được số 𝑥 của mình. Điều mà Nhật Khôi vẫn còn nhớ trong đầu đó là số 𝑓₀ đầu tiên chắc chắn là số 0 và số 𝑛 và giá trị 𝑓_𝑛. Nhưng Nhật Khôi đã quên số 𝑥 rồi.

Yêu cầu: Hãy giúp Nhật Khôi tìm lại số 𝑥 của mình nhé!!!

Dữ liệu: Vào từ file văn bản FIBONACCI.INP gồm hai số là lượt là 𝑛 và 𝑓_𝑛  (2 ≤ 𝑛 ≤ 1000).

Kết quả: Ghi ra file văn bản FIBONACCI.OUT gồm một số nguyên duy nhất là số 𝑥.

Ràng buộc:

·         Có 40% số lượng tests thỏa mãn điều kiện: 0 ≤ 𝑓_𝑛  ≤ 1000000;

·         60% số lượng tests còn lại thỏa mãn điều kiện: 0 ≤ 𝑓_𝑛 ≤ 10¹⁸.

Ví dụ:

FIBONACCI.INP	FIBONACCI.OUT
6 8	1

 Test

GIẢ THUYẾT GOLDBACH

Nguồn: Bắc bộ 2015

Giả thuyết Goldbach cho rằng: Tất cả các số tự nhiên chẵn lớn hơn 2 đều có thể được biểu diễn     dưới dạng tổng của 2 số nguyên  tố. Gọi G(N) là số các cách biểu diễn  khác nhau số 2N dưới   dạng tổng 2 số nguyên tố. Cho N (3 ≤ N ≤ 500,000), hãy tính F(N) = G(2) + G(3) + … + G(N).

Input: gồm không quá 30 bộ tests, mỗi bộ test được ghi trên một dòng: số nguyên N.

Output:  Ứng với mỗi bộ test, ghi ra trên một dòng giá trị F(N) tương ứng.

Ví dụ:

GOLDBACH.INP	GOLDBACH.OUT
7 4 9	8 3 12

 Test - code - solution -đề (word)

POWER

Nguồn: Bắc Bộ 2015

Số nguyên x được gọi là số lũy thừa đúng nếu tồn tại hai số nguyên a và b (b > 1), sao cho x=a^b. Ví dụ, 16 là một số lũy thừa đúng vì 16 = 2⁴. 

Việc biểu diễn x dưới dạng lũy thừa có thể không duy nhất. Ví dụ 16 = 2⁴ = 4². Như vậy, với x=16 tồn tại 2 cặp số (a, b) biễu diễn nó.

Yêu cầu: Cho số nguyên x (1 ≤ x ≤ 10¹⁸). Hãy tìm tất cả các cặp số nguyên (a, b) thỏa mãn x=a^b.

Input:  POWER.INP

-         Dòng 1: Số nguyên x (1 ≤ x ≤ 10¹⁸)

Output: POWER.OUT

-         Số nguyên k – số cặp (a, b) tìm được

-         Nếu k>0, mỗi dòng trong k dòng sau chứa 2 số nguyên a và b

POWER.INP	POWER.OUT
16	2 2 4 4 2

 Test - code (pascal) - code (C++) - solution - đề (word)

SỐ NGUYÊN TỐ

Nguồn: Chuyên Hoàng Văn Thụ - Hòa Bình

Cho dãy số nguyên x₁, x₂, …, x_N và hàm f(p) là số lượng các phần tử thuộc dãy x chia hết cho p.

Cho M truy vấn, mỗi truy vấn cho hai số nguyên l_i, r_i. Bạn phải trả lời câu hỏi: Tính tổng:

 , ở đây S(l_i, r_i) là tập các số nguyên tố thuộc đoạn [l_i,r_i].

INPUT:

·         Dòng đầu tiên chứa giá trị N (1 ≤ N ≤ 10⁶)

·         Dòng hai chứa N số nguyên x₁, x₂, …, x_N (2 ≤ x_i ≤ 10⁵)

·         Dòng ba chứa giá trị M (1 ≤ M ≤ 5*10⁴)

·         M dòng tiếp theo, mỗi dòng chứa hai số l_i, r_i (2 ≤ l_i ≤ r_i ≤ 2*10⁹)

OUTPUT:

·         Gồm M dòng, mỗi dòng là câu trả lời của truy vấn tương ứng của INPUT.

Ví dụ:

PRIME.INP	PRIME.OUT
6 5 5 7 10 14 15 3 2 11 3 12 4 4	9 7 0

Giải thích:

·         Tại truy vấn 1: l = 2, r = 11:

Ta cần tính f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.

·         Tại truy vấn 2: l = 3, r = 12:

Ta cần tính f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7

·         Tại truy vấn 3: l = 4, r = 4: không có số nguyên tố nào thuộc đoạn [l,r], nên kết quả truy vấn bằng 0

* Chú ý:

·         40% test 1 ≤ N, M ≤ 100; 1 ≤ l_i ≤ r_i ≤ 1000

·         40% test tiếp theo 1 ≤ N, M ≤ 1000; 1 ≤ l_i ≤ r_i ≤ 1000

·         20% test còn lại 1 ≤ N ≤ 10⁶, 2 ≤ x_i ≤ 10⁵, 1 ≤ M ≤ 5*10⁴, 2 ≤ l_i ≤ r_i ≤ 2*10⁹

 Test - Code - Solution - đề (word)

Kiểm tra số nguyên tố

Cho số nguyên dương n và dãy n số nguyên dương a₁, a₂,…,a_n. Hãy cho biết số a_i có phải là số nguyên tố hay không?

Dữ liệu vào: Từ tệp văn bản CPRIME.INP

+ Dòng đầu tiên ghi số nguyên dương n

+ Dòng thứ 2 ghi n số nguyên dương a₁, a₂,…,a_n

Dữ liệu ra: ghi vào tệp văn bản CPRIME.OUT gồm n dòng, trong đó dòng thứ i ghi YES nếu số a_i là số nguyên tố, ngược lại ghi NO

Ví dụ:

CPRIME.INP	CPRIME.OUT
3 1 4 7	NO NO YES

Giới hạn:

+ 1≤n≤10⁶

+ 1≤a_i≤10⁷

Test – code

Chương trình tạo test

Chương trình tạo test cho bài Kiểm tra số nguyên tố

Bao gồm 4 test, đánh số từ 00 đến 03

Mỗi test có quy cách: 

+ Dòng đầu tiên ghi số nguyên dương n

+ Dòng thứ 2 ghi n số nguyên dương a1, a2,…,an

Gới hạn:

+ 1≤n≤10^6

+ 1≤ai≤10^7

BỘ SỐ PY – TA – GO

Một bộ ba số tự nhiên được gọi là bộ số Py-ta-go nếu thỏa mãn điều kiện : bình phương một số bằng tổng bình phương hai số còn lại.

Ví dụ: Bộ số (3, 4, 5) là một bộ số Pytago vì : 5²=3²+4².

Yêu cầu: Cho số nguyên dương N. Hãy phân tích N thành tổng của một bộ Pytago

Dữ liệu vào: Từ tệp PYTAGO.INP chứa số nguyên N (1≤N≤10⁶)

Kết quả ra:  ghi vào tệp PYTAGO.OUT số lượng bộ số Pytago tách được

Ví dụ :

PYTAGO.INP	PYTAGO.OUT	Giải thích
30	1	132=52+122

Tính sai

Nguồn bài: http://vn.spoj.com/problems/WCALC/

Khi còn bé, các bạn học sinh học được cách trừ phân số bằng cách quy đồng mẫu số, rồi mới thực hiện phép trừ:  

Nhưng một lần, An tính thử hiệu hai phân số bằng cách lấy hiệu hai tử số và hiệu hai mẫu số và thấy thật ngạc nhiên là kết quả vẫn đúng: 

An thấy tính chất này thật kỳ diệu và An muốn biết, với phân số cho trước, có bao nhiêu cặp giá trị  a>=0 và m>=0 sao cho: 

Dữ liệu vào: từ tệp văn bản WCALC.INP: Một dòng chứa hai số nguyên dương b và n cách nhau ít nhất một dấu cách (1 <= b, n <= 10^6; trong 50% số test b, n <= 1000).

Dữ liệu ra: ghi vào tệp văn bản WCALC.OUT một số nguyên duy nhất là số lượng cặp (a,m) tính được.

Ví dụ:

WCALC.INP	WCALC.OUT
9 12	5

TÌM CHỮ SỐ

Xét biểu diễn thập phân của phân số a/b. Biểu diễn này có thể là một số thập phân hữu hạn hoặc một số thập phân vô hạn tuần hoàn. Nếu phân số có thể biểu diễn bởi một số thập phân hữu hạn, ta có thể viết thêm một dãy vô hạn các chữ số 0 vào sau chữ số cuối cùng sau dấu chấm thập phân và coi đó cũng là một số thập phân vô hạn tuần hoàn. Ví dụ:

Yêu cầu: Sau khi đánh số từ 1 trở đi, từ trái qua phải các chữ số đứng sau dấu “,” trong biểu diễn thập phân của a/b, hãy xác định chữ số thứ k.

Ví dụ:

+ Với a=100, b=8, k=2, chữ số đứng thứ 2 sau dấu thập phân của giá trị 100/8  là chữ số 0

+ Với a=99, b=140, k=12, chữ số đứng thứ 12 sau dấu chấm thập phân giá trị 99/140 là chữ số 2

Dữ liệu: Vào từ tệp văn bản DIGIT.INP gồm 1 dòng chứa 3 số nguyên dương a, b, k<= 10^18 cách nhau ít nhất một ký tự trắng.

Kết quả: Ghi ra tệp văn bản DIGIT.OUT một số nguyên duy nhất là giá trị chữ số tìm được

Ví dụ:

DIGIT.INP	DIGIT.OUT
100 8 1	5
17 3 10	6
99 140 12	2

CHIA BÁNH

Bạn muốn chia n cái bánh cho m người, ban đầu mỗi cái bánh là một phần. Công cụ duy nhất bạn có là một dao cắt bánh, ở mỗi thao tác cắt, bạn được chia một phần bánh thành 2 phần với tỉ lệ tùy ý. Hãy tìm cách dùng ít thao tác nhất để chia bánh thành các phần chia cho m người, mỗi phần thuộc về đúng một người và lượng bánh mỗi người được nhận là bằng nhau.

Dữ liệu vào: Từ tệp văn bản SHARE.INP gồm một dòng chứa hai số nguyên dương n, m ≤10¹⁸

Kết quả: Ghi vào tệp văn bản SHARE.OUT một số nguyên duy nhất là số thao tác phải sử dụng.

Ví dụ:

SHARE.INP	SHARE.OUT
3 5	4

SỐ PINARY

Pinary là số nguyên chứa các số 0 và 1 thoả mãn các điều kiện:

+ Không bắt đầu bằng 0,

+ Không chứa 2 số 1 liên tiếp nhau.

Ví dụ, các số sau là số Pinary: 1, 10, 100, 101, 1000, 1001, 1010, . . . Còn các số sau không phải là Pinary: 00101, 1001101.

Các số Pinary được sắp xếp theo thứ tự từ điển.

Yêu cầu: Cho số nguyên n. Hãy xác định số Pinary thứ n.

Dữ liệu: Vào từ file văn bản PINARY.INP gồm nhiều dòng, mỗi dòng chứa một số nguyên n (0<n≤90000000).

Kết quả: Đưa ra file văn bản PINARY.OUT các số Pinary tìm được, mỗi số trên một dòng.

Ví dụ:

PINARY.INP	PINARY.OUT
7 2000 22	1010 1001000001001000 1000001

SOLUTION - TEST - CODE