Giúp mình giải thuật giải bài dựng hình

note ở đây cuối tuần làm :))) nhưng chắc là sử dụng tính chia hết để kiểm tra

Bài này có ít nhất là 2 cách làm:

• Dùng toán: nếu góc gọi g = GCD(x, 360), thì ta có thể thấy rằng, mọi góc mà là bội của g thì sẽ tạo được bằng cách lấy nhiều lần x. Như vậy, nếu ta tính GCD của các góc Tí vẽ được với 360, sẽ ra góc đơn vị nhỏ nhất mà Tí có thể vẽ được. Và mọi góc mà Tí vẽ được đều chia hết cho góc này. Sau đó đọc từng số trong K số yêu cầu, nếu nó chia hết cho góc đơn vị thì YES, ngược lại NO. Độ phức tạp: O(Nlog360 + K)
• Dùng Quy hoạch động: gọi F[i] đánh dấu là Tí vẽ được góc i hay không. Dễ thấy, nếu ta chọn ra 1 cặp góc (x, y) bất kì, thì có thể vẽ được 2 góc (x+y) và (x-y). Và mặc định góc 0^o là luôn vẽ được. Nêu khi đọc từng số a trong n số, ta sẽ lặp, duyệt từ 0 đến 360, nếu i đã vẽ được, thì ta thấy có thể vẽ thêm góc (i+a) và (i-a), nếu 2 góc chưa được vẽ thì ta vẽ và đánh dấu là có góc mới. Ta cứ lặp như vậy cho đến khi nào hết vẽ được góc mới thì thôi. Dễ thấy, sau khi xử lý hết N số ban đầu, tổng số vòng lặp tối đa là 360 (vì mỗi góc chỉ vẽ 1 lần, 360 góc mới thì tối đa 360 vòng lặp để vẽ). Khi đã có mảng F thì việc trả lời câu hỏi chỉ cần O(1) cho mỗi câu hỏi. Nên độ phức tạp là O(360² + K).

Mà lần sau post bài thì nhớ post luôn cái đề nhá, chơi post input output cho người ta đoán đề à :v