• Bài này đơn giản chỉ cần if...else... theo đề

https://youtu.be/s4SoTOof2Yk

• Sắp xếp, tham lam

• Chọn m số đầu tiên sao cho S[m]<=k với S[i] là tổng cộng dồn i số đầu tiên.

https://youtu.be/s4SoTOof2Yk

• Xử lí xâu cơ bản

• Tách từng số gồm các kí tự số liên tiếp

• Chuẩn hoá xâu thành số

• Đếm số lần xuất hiện của từng số bằng map

• In đáp án là số lượng các số xuất hiện đúng 1 lần

https://youtu.be/TfgwYMUMNkw

• Trâu: Duyệt mọi cặp (i,j), kiểm tra điều kiện và tìm giá trị nhỏ nhất.

• Tối ưu bằng hai con trỏ:

  • Sắp xếp A, B tăng dần

  • Con trỏ i ở đầu dãy A, j ở đầu dãy B

    • ans = min(ans, abs(A[i]-B[j])

    • Nếu A[i]<B[j] thì hiệu sẽ là B[j]-A[i]; muốn hiệu này nhỏ hơn thì tăng A[i] tức là i++ (vì dãy A tăng dần)

    • Ngược lại thì tăng j++ (vì dãy B tăng dần)

https://youtu.be/dXdJDwPQ-kE

• Ý tưởng chung:

  • Duyệt từng số x trong [a,b]

    • Kiểm tra x có là số siêu nguyên tố không, nếu là số snt thì đếm.

• Sub1. Kiểm tra tính nguyên tố bằng định nghĩa, thuật toán O(sqrt(n))

• Sub2, Sub3: Cải tiến bằng dùng sàng nguyên tố O(n log log n)

• Sub4: với b<=10^12

  • Không thể duyệt từng số trong đoạn

  • Sinh ra mọi số siêu nguyên tố y <=b --> đếm++

https://youtu.be/ac-v6NU7alE

• Hàm sinh số siêu nguyên tố bắt đầu từ số nguyên tố x:

  • Nếu a<=x<=b và x>10 thì đếm (vì đề bài chỉ yêu cầu đếm số siêu nguyên tố lớn hơn 10)

  • Nối dần vào x các chữ số nguyên tố d: {1, 3, 7, 9} để được số y=x*10+d:

    • Nếu y>b thì xét tiếp

    • Ngược lại:

      • Nếu y là số nguyên tố:

        • Sinh tiếp từ y.

void dfs(int64 x) {

// Chỉ đếm số > 10 theo đề bài

if (x >= a && x <= b && x > 10) {

ans++;

}

// Chữ số cuối của số nguyên tố > 10 chỉ có thể là 1, 3, 7, 9

int digit[] = {1, 3, 7, 9};

for (int d : digit) {

int64 y = x * 10 + d;

if (y > b) continue;

if (isPrime(y)) {

dfs(y);

}

}

}