Ta nhận thấy đây là 1 đa giác đều có số đỉnh là số chẵn nên nếu ta chọn 1 điểm bất kì và kẻ 1 đường kính đi qua điểm này thì đường kính này cũng sẽ đi qua 1 điểm khác của đa giác. Do đó, ta sẽ làm như sau: - Đầu tiên, chọn 1 trong n đỉnh của đa giác này có n cách. - Tiếp theo, kẻ 1 đường kính đi qua điểm này. Để tạo thành được 1 tam giác tù thì 2 điểm còn lại mà ta chọn sẽ phải nằm ở cùng 1 phía so với đường kính ta kẻ và ta sẽ chỉ chọn các điểm ở 1 phía của đường kính này thôi do nếu chọn ở cả 2 phía thì khi đến điểm đối xứng với điểm mà ta chọn trước đó sẽ bị trùng lặp. Nhiều bạn sẽ băn khoăn rằng chọn 2 điểm ở 2 bên cũng được 1 tam giác tù mà nhưng chọn như vậy lại giống ở trên, chúng ta sẽ bị trùng lặp các hình do việc đếm mà không có quy tắc nhất định. Số cách để chọn 2 điểm trong $$$m = \dfrac{n - 2} {2}$$$ điểm còn lại ở 1 phía là $$$C_m^2$$$ cách = $$$\dfrac{m * (m - 1)} {2}$$$.

$$$\Rightarrow$$$ Vậy số tam giác tù sẽ là $$$\dfrac{n * m * (m - 1)} {2}$$$.

https://ideone.com/7FohWY

• Nhập cho đến khi không nhập được nữa dùng While(cin >> n){ }. cin >> n sẽ có giá trị true nếu cin đọc vào được
• Bài này tư duy xuất phát từ cách vẽ hình vuông có 2 đường chéo và thêm 1 số điều kiện để vẽ được chữ M thoả mãn
• Cần lưu ý một số trường hợp n nhập vào không vẽ được hình thoả mãn như n=4,n=3,...

https://ideone.com/H0TNVI

- Ta có thể thấy được là các số duy nhất có 3 ước số là các bình phương của các số nguyên tố .

Vd:     9 có ước là { 1, 3 ,9 }

          25 có ước là { 1, 5, 25 }

⇒ Từ đó có thể thấy được là yêu cầu của bài toán đang muốn ta đếm các số mà khi căn ra ta sẽ có 1 số nguyên tố trong khoảng [l, r] .

Tuy nhiên khi ta chú ý vào phần giới hạn của đề bài: 1 ≤ T ≤ 100; 1 ≤ l, r ≤ $$$10^{12}$$$. Nếu ta duyệt trâu từ l đến r thì Code của chúng ta sẽ bị TLE (Time Limit Exceed).

Giải pháp:  Vì số đang tìm là bình phương của các số nguyên tố, nên ta sẽ đơn giản hóa bài toán thành “Đếm các số nguyên tố trong khoảng [ $$$\sqrt{l}$$$ , $$$\sqrt{r}$$$ ]” 

Chú ý: $$$\sqrt{l}$$$ đôi khi sẽ là số thập phân nên ta sẽ phải làm tròn lên thay vì làm tròn xuống để ta sẽ không bị dính lỗi như sau:
vd: $$$\sqrt{10}$$$ = 3.1623 khi làm tròn xuống nó sẽ thành 3 mà 3 cũng là số nguyên tố nên khi đếm thì 3 cũng sẽ được tính vào kết quả, mà khoảng $$$\sqrt{l}$$$ thực của chúng ta là 3.1623 > 3. Chính vì thế ta bắt đầu đếm từ 4 để tránh lỗi này.

Hàm làm tròn lên là ceil().

https://ideone.com/62n8tr

Trường hợp không thể đong:

• Trường hợp không thể đong được là khi không có cách kết hợp giữa hai bao gạo để đạt được n kg. Một trường hợp đặc biệt dễ nhận thấy là:
  • Nếu m chia hết cho 3 nhưng n không chia hết cho 3, thì không thể đong được vì không có cách nào sử dụng bao 3 kg để bù phần dư.
  • Trường hợp này sẽ đưa ra kết quả -1.

Chiến lược tối ưu số lần đong:

• Giả sử ta có hai loại bao đong 3 kg và m kg. Ý tưởng chính là thử sử dụng bao lớn hơn (bao có trọng lượng lớn hơn giữa 3 và m) nhiều nhất có thể để đong được gần bằng hoặc đúng n kg, sau đó sử dụng bao nhỏ hơn để đong nốt phần còn lại.
• Ví dụ: Nếu bạn dùng bao lớn nhất (MAX kg), hãy tính số lần có thể dùng bao này để lấy gần nhất với n kg mà vẫn còn dư một lượng có thể đong bằng bao nhỏ hơn (MIN kg).

https://ideone.com/5ZXY7H

• Bài này rất dễ các bạn chỉ cần hiểu đề bài rằng có tổng cộng T cánh cửa (Test Case) và 1 số H ban đầu, với mỗi Test như thế bạn chỉ cần kiểm tra xem H có lớn hơn tất cả các số có tổng các chữ số (khác 0) = n hay không. Nếu có cập nhật H — số số thoả mãn + k, nếu không thoát khỏi vòng lặp.
• Nếu muốn biết số số thoả mãn điều kiện thì hãy thử nháp hoặc xem code.

https://ideone.com/VZWQ9f