Que diêm độ dài L chỉ để vừa hộp nếu độ dài nhỏ hơn hoặc bẳng đường chéo của HCN

Chỉ cần kiểm tra L^2 = W^2 + H^2

Giả sử đoạn liên tiếp các kí tự giống nhau có độ dài là len à để 2 kí tự kề nhau trong đoạn khác nhau thì cần đổi ít nhất len/2 lần. 

Muốn số đoạn nhiều nhất thì nên chia thành các đoạn ngắn nhất có thể miễn là vẫn hợp lệ.

Bài toán trở thành: Đếm số đoạn con (l,r) liên tiếp thoả mãn gcd đoạn=1.

 Lưu ý: định nghĩa gcd của dãy gồm 1 phần tử bằng chính nó; vd: gcd(3)=3

Tóm tắt: Đếm số cặp i, j sao cho A[i]*B[j]=k

Sub1: Duyệt mọi cặp (i,j), kiểm tra điều kiện và đếm

Sub2,3:

• Với mỗi A[i]: 

  • B[j]=k/A[i]

  • Nếu k chia hết cho A[i] và số lần xuất hiện k/A[i] trong B là x thì số lượng cặp (i,j) là ans+=x

Gợi ý: Đếm bằng mảng tần suất, cải tiến bằng map, unordered_map 

Gọi cnt[x]=số lượng phần tử có giá trị x

Sinh ra các số đẹp s

Với mỗi A[i]:

• Xét các số đẹp s:

  • Tính need = s – A[i]

  • Nếu need đã xuất hiện trước đó thì ans+=cnt[need]

• Ghi nhận xuất hiện của A[i] bằng cnt[A[i]]++