[Buổi 2] Số nguyên tố Q, Sức mạnh, Mật mã, Dãy số tương đương

 

Câu 1. Số nguyên tố Q

Đề bài

Phân tích

Input:

- Một số nguyên dương N (rất lớn, tối đa 5×10¹⁷ ⇒ nên đọc chuỗi thay vì kiểu số).

- Một số Q (0 < Q ≤ 9): yêu cầu tìm chữ số nhỏ thứ Q trong N (sắp xếp tăng dần theo giá trị chữ số).

Output:

- Chữ số nhỏ thứ Q đó (nếu tồn tại), và kiểm tra có phải số nguyên tố không.

- Nếu không có chữ số nhỏ thứ Q thì in -1.

Cấu trúc dữ liệu sử dụng

- Đọc N dưới dạng chuỗi (tránh lỗi tràn số).

- Tạo list chữ số từ N → sắp xếp tăng dần → tìm phần tử thứ Q.

- Số nguyên tố 1 chữ số: 2, 3, 5, 7.

Code mẫu

fi=open("SONTTQ.INP")
fo=open("SONTTQ.OUT","w")
N=fi.readline().strip()
Q=int(fi.readline().strip())
#Loại bỏ chữ số trùng
#Sắp xếp tăng dần, các phần tử cho vào mảng a
a=sorted(set(int(c) for c in N))

if Q<=len(a):
    kq=f"{a[Q-1]} {'Yes' if a[Q-1] in {2, 3, 5, 7} else 'No'}"
else:
    kq=-1

fo.write(kq)

fi.close()
fo.close()

Câu 2. Sức mạnh 

Đề bài

Phân tích

- Người chơi gặp q con thú, mỗi con có giá trị ai.

- Sức mạnh của con thú thứ i là tổng tất cả ước nguyên dương của ai.

Ví dụ: a = 4 ⇒ Ước: 1, 2, 4 ⇒ Tổng = 7.

Cấu trúc dữ liệu sử dụng

- List để lưu giá trị các con thú.

- Hàm tính tổng ước cho mỗi số.

Code mẫu

import math
def G(n):
    s = 0
    for i in range(1, int(math.isqrt(n)) + 1):
        if n % i == 0:
            s += i
            if i != n // i:
                s += n // i
    return s
fi=open("SMTHU.INP")
fo=open("SMTHU.OUT","w")
q = int(fi.readline())
a = list(map(int, fi.readline().split()))

sm=[G(ai) for ai in a]

fo.write(' '.join(map(str, sm)))

fi.close()
fo.close()

Câu 3. Mật mã

Đề bài

Phân tích

- Một xâu ký tự s gồm: Chữ cái (a-z, A-Z); Chữ số (0-9); Khoảng trắng (' ' — có thể nhiều)

- Khóa mở hòm tài liệu = Tổng các chữ số xuất hiện trong xâu.

- Thông tin triển khai = Các từ đảo ngược, chỉ gồm chữ cái (bỏ chữ số).

Cấu trúc dữ liệu sử dụng

- Biến: cộng dồn các chữ số trong xâu.

- List: để chứa các từ đã xử lý (bỏ số, đảo ngược).

Code mẫu

import re
fi=open("MATMA.INP")
fo=open("MATMA.OUT","w")
s = fi.readline().strip()
#Cộng các chữ số
tong = sum(int(c) for c in s if c.isdigit())
#Xử lí chuổi
s=re.sub(r'\d', '', s)
a = s.split()
kq=[]
for ai in a:
    kq.append(ai[::-1])
fo.write(f"{tong} {' '.join(kq)}")
fi.close()
fo.close()

Câu 4. Dãy số tương đương

Đề bài

Phân tích

Cấu trúc dữ liệu sử dụng

Code mẫu

from collections import Counter
def phan_tich(a):
    ai_mu = Counter()
    for ai in a:
        d = 2
        while d * d <= ai:
            while ai % d == 0:
                ai_mu[d] += 1
                ai //= d
            d += 1
        if ai > 1:
            ai_mu[ai] += 1
    return ai_mu

fi=open("TTICH.INP")
fo=open("TTICH.OUT","w")

dong = fi.read().splitlines()
idx=0
t=int(dong[0])
kq=[]
for i in range(t):
    idx +=1
    n,m=map(int, dong[idx].split())
    idx+=1
    A = list(map(int, dong[idx].split()))
    idx+=1
    B = list(map(int, dong[idx].split()))
    pta = phan_tich(A)
    ptb = phan_tich(B)
    if pta==ptb:
        kq.append("Yes")
    else:
        kq.append("No")

fo.write('\n'.join(kq))

fi.close()
fo.close()