Để tạo được 1 hình chữ nhật thì ta cần phải có 2 cặp đường thẳng:

• Mỗi cặp sẽ gồm 2 đường thẳng song song với nhau và 2 cặp đường thẳng này phải vuông góc với nhau (tức là mọi đường thẳng ở trong cặp này phải vuông góc với mọi đường thẳng ở trong cặp kia).

• Đối với lưới ô vuông có kích thước m x n, ta thấy có m + 1 đường thẳng đôi một song song với nhau theo chiều ngang và n + 1 đường thẳng đôi một song song với nhau theo chiều dọc, các đường thẳng theo chiều ngang sẽ vuông góc với các đường thẳng theo chiều dọc do đó nếu ta chọn 2 đường thẳng theo chiều ngang và 2 đường thẳng theo chiều dọc sẽ tạo được 1 hình chữ nhật. $$$\Rightarrow$$$ Vậy số hình chữ nhật sẽ là:

https://ideone.com/vcsO7q

Bài toán yêu cầu đếm số lượng ước nguyên tố của một số nguyên dương n. Ý tưởng chính của đoạn code này là thử chia các số từ 2 đến √n để xác định các ước nguyên tố, rồi loại bỏ các thừa số nguyên tố đã tìm được khỏi n. Sau đó, nếu n vẫn còn lớn hơn 1, ta sẽ đếm n là một ước nguyên tố lớn hơn √n.

Ý tưởng chi tiết:

1. Thử chia từ 2 đến √n:

• Vì một số nguyên n chỉ có thể có các ước nguyên tố nhỏ hơn hoặc bằng √n (nếu tồn tại), nên ta chỉ cần kiểm tra các số từ 2 đến √n.
• Khi một số i chia hết cho n, điều đó có nghĩa là i là một ước nguyên tố của n.
• Sau khi xác định một ước nguyên tố, ta cần loại bỏ tất cả các bội của số đó khỏi n (tức là chia n liên tục cho i cho đến khi n không chia hết cho i nữa).

2. Kiểm tra số còn lại:

• Sau khi thử hết các số từ 2 đến √n, nếu giá trị của n vẫn còn lớn hơn 1, thì n còn lại chính là một ước nguyên tố lớn hơn √n. Lúc này ta đếm nó là một ước nguyên tố.

3. In kết quả: Sau khi đếm xong, in ra số lượng ước nguyên tố của n.

https://ideone.com/HRpJPc

• Vận dụng thực tế một chút, có 2 người đứng ở 2 vị trí khác nhau và kéo một sợi dây không dãn căng nhất có thể thì lúc này chiều dài sợi dây tính từ vị trí của người 1 đến người 2 sẽ là khoảng cách ngắn nhất giữa 2 người. Do đó với bài này, ta hình dung là có 1 người đứng ở vị trí xuất phát và 1 người đứng ở điểm đặt Spike và 2 người kéo căng sợi dây không dãn nêu trên thì chiều dài sợi dây từ vị trí người 1 đến vị trí người 2 sẽ là kết quả cần tìm. Từ điểm O, ta kẻ 2 tiếp tuyến với đường tròn trên và nhận thấy 2 tiếp tuyến này đều không đi vào miền kẻ màu xanh nên sợi dây này sẽ phải vắt qua đường tròn (tức là việc đi trên con đường ngắn nhất này sẽ phải đi một chút trên viền đường tròn).
• Đến đây, ta có 2 cách vắt sợi dây qua đường tròn rồi kéo căng (ở trên hoặc ở dưới). Gọi O là điểm xuất phát, I là tâm đường tròn và K là điểm tới. Con đường ngắn nhất sẽ là con đường mà I nhìn dưới một góc < 180 độ. Gọi A và B là 2 điểm mà con đường ngắn nhất tiếp tuyến với đường tròn, L là kết quả. Ta có, L = OA + độ dài cung AB + BK. Chi tiết về việc tính toán và giải thích cụ thể ở từng bước tính các bạn có thể xem ở phần code dưới đây. Chỗ nào không hiểu có thể hỏi anh chị mentor.

https://ideone.com/5ryKnq

• 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ẽ tam giác vuông và ghép bởi 2 tam giác vuông úp lên nhau và thêm 1 số điều kiện để thoả mãn hình vẽ
• 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=3,n=2,...

https://ideone.com/LjN27p

Nhận thấy các số đều có thể phân tích thành dạng: 

       $$$Số = k * div + i$$$

Với:

• k là hệ số : 0, 1, 2 ..
• div là số để chia
• i là phần dư

Khi ta bình phương số đó:

       $$$(Số)^2 = số * số = (k * div + i) * (k * div + i)$$$

$$$k*div$$$ là một số chia hết cho $$$mod$$$

Khi chia dư cho mod:

       $$$(Số)^2$$$ % mod  = ( (k * div + i) % mod) * ( (k * div + i) % mod)

                                = ( (0 + i % mod) *  (0 + i % mod))

                                = $$$i^2$$$ % mod

Khi tìm số bình phương chia dư cho mod dư 1 => tìm số có phần dư i bình phương chia dư cho mod dư 1.

Nên khi tìm được $$$i^2$$$ % mod == 1 => đếm các số có dạng k * div + i;

Với k là hệ số, div là số để chia, i là số dư

⇒Vậy mục đích đề bài trở thành trong đoạn phần dư từ 1 đến $$$div - 1$$$. Tìm các số có dạng $$$k * div + i$$$ với điều kiện $$$i^2$$$ % mod == 1

https://ideone.com/hbZU2y