Luyện Tập #22

Xét dãy số vô hạn:

1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ...

Dãy được xây dựng như sau: đầu tiên viết số 1, sau đó viết các số từ 1 đến 2, tiếp theo là các số từ 1 đến 3, rồi từ 1 đến 4, và cứ tiếp tục như vậy.

Lưu ý rằng dãy gồm các số, không phải các chữ số. Ví dụ, số 10 xuất hiện lần đầu tiên ở vị trí 55 của dãy (các phần tử được đánh số từ 1).

Yêu cầu

• Tìm số nằm ở vị trí thứ n trong dãy.

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên n (1 ≤ n ≤ 10^14).
• Giá trị n rất lớn, cần sử dụng kiểu số nguyên 64-bit để lưu trữ.

Kết quả

• In ra phần tử ở vị trí thứ n trong dãy.

Ví dụ

Có một bộ đếm đặc biệt.

Ở giây đầu tiên, bộ đếm hiển thị số 3. Mỗi giây tiếp theo, giá trị hiển thị giảm đi 1 cho đến khi đạt 1.

Ở giây kế tiếp sau khi đạt 1, bộ đếm bắt đầu một chu kỳ mới với giá trị ban đầu bằng 2 lần giá trị ban đầu của chu kỳ trước, rồi tiếp tục giảm dần.

Ví dụ, các giá trị đầu tiên của bộ đếm là:

3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, ...

Yêu cầu

• Cho thời điểm t, hãy tìm giá trị được hiển thị trên bộ đếm tại thời điểm đó.

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên t (1 ≤ t ≤ 10^12).

Kết quả

• In ra giá trị được hiển thị trên bộ đếm tại thời điểm t.

Chấm điểm

• 60% số điểm với 1 ≤ t ≤ 10^5.

Ví dụ

Với số nguyên dương n, định nghĩa hàm:

f(n) = -1 + 2 - 3 + 4 - ... + (-1)^n × n

Yêu cầu

• Cho số nguyên n, hãy tính giá trị f(n).

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên dương n (1 ≤ n ≤ 10^15).

Kết quả

• In ra giá trị f(n).

Ví dụ

Mehrdad phải giải một câu hỏi trong kỳ thi:

Cho số nguyên n, hãy tìm chữ số cuối cùng của 1378^n.

Yêu cầu

• Tìm chữ số cuối cùng của 1378^n.

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên n (0 ≤ n ≤ 10^9).

Kết quả

• In ra một số nguyên duy nhất là chữ số cuối cùng của 1378^n.

Ví dụ

Cho số nguyên N.

Với mỗi số nguyên dương x, định nghĩa f(x) là số lượng số nguyên dương không vượt quá x và có cùng số chữ số với x.

Yêu cầu

• Tính:

f(1) + f(2) + ... + f(N)

• In ra phần dư của kết quả khi chia cho 998244353.

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên N.
• 1 ≤ N < 10^18.

Kết quả

• In ra kết quả modulo 998244353.

Ví dụ

Xét các cấp số cộng gồm các số nguyên có công sai bằng 1.

Yêu cầu

• Cho số nguyên N, hãy đếm xem có bao nhiêu cấp số cộng như vậy có tổng các phần tử bằng N.

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên N.
• 1 ≤ N ≤ 10^12.

Kết quả

• In ra số lượng cấp số cộng thỏa mãn.

Ví dụ

Cho một số nguyên dương N.

Ta có thể thực hiện lặp lại thao tác sau:

• Chọn một số nguyên dương z thỏa mãn tất cả các điều kiện:
• z có dạng p^e, trong đó p là số nguyên tố và e là số nguyên dương.
• N chia hết cho z.
• z khác với tất cả các số đã chọn trong những thao tác trước.
• Sau đó thay N bằng N / z.

Yêu cầu

• Tìm số lần thực hiện thao tác lớn nhất có thể.

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên N (1 ≤ N ≤ 10^12).

Kết quả

• In ra số lần thực hiện thao tác lớn nhất.

Ví dụ