FINDING RABBIT
View as PDFRabbit đã đi lạc trong rừng mất rồi! Và Tigger sẽ phải đi tìm cậu ta. Tìm kiếm một hồi lâu, Tigger dừng chân trước một con sông. Sau khi quan sát xung quanh, Tigger nhận thấy, chỉ có một cách duy nhất để qua sông đó là nhảy qua các hòn đá. Có ~n~ hòn đá xếp thẳng hàng, vuông góc giữa hai bờ sông. Hòn đá thứ ~i~ có độ cao ~h_i~. Ngoài ra, bờ sông Tigger đang đứng có một hòn đá có độ cao là ~0~ và được đánh số là ~0~. Đương nhiên, việc qua sông là vô cùng đơn giản với Tigger. Tigger muốn hành trình của mình trở nên thử thách hơn và cậu quyết định sẽ chỉ nhảy từ ô thứ ~i~ tới ô thứ ~j > i~ nếu tồn tại một số nguyên ~x > 1~ là ước chung của ~h_i~ và ~h_j~. 'Nhưng thế này thì vẫn còn dễ quá!' - Tigger nghĩ bụng. Vì thế, cậu muốn nhảy tới mỗi hòn đá bằng nhiều cách khác nhau. Hãy tính thử xem với mỗi hòn đá, có bao nhiêu cách để Tigger nhảy từ bờ sông Tigger đang đứng tới hòn đá đó nhé.
INPUT
- Dòng đầu tiên gồm một số nguyên dương ~n~ là số lượng hòn đá.
- Dòng thứ hai gồm n số nguyên dương ~h_1, h_2, ..., h_n (h_i ≤ 1000000)~ là độ cao của các hòn đá.
OUTPUT
- Gồm ~n~ số nguyên không âm, là số cách nhảy từ bờ sông Tigger đang đứng tới hòn đá thứ ~i~, vì kết quả có thể rất lớn nên hãy in ra kết quả chia lấy dư cho ~918052004~.
Ví dụ
Input 1
5
2 4 3 6 5
Output 1
1 2 1 5 1
Giải thích:
- Hòn đá thứ 1: có ~1~ cách nhảy là ~0 → 1~
- Hòn đá thứ 2: có ~2~ cách nhảy là ~0 → 1 → 2~ và ~0 → 2~
- Hòn đá thứ 3: có ~1~ cách nhảy là ~0 → 3~
- Hòn đá thứ 4: có ~5~ cách nhảy là ~0 → 1 → 2 → 4, 0 → 1 → 4, 0 → 2 → 4, 0 → 3 → 4~ và ~0 → 4~
- Hòn đá thứ 5: có ~1~ cách nhảy là ~0 → 5~
Subtask 1: 30% số test thỏa ~n ≤ 20~;
Subtask 2: 40% số test thỏa ~n ≤ 2000~;
Subtask 3: 30% số test thỏa ~n ≤ 200000~;
https://www.youtube.com/watch?v=h5aQ7Yoh3PI
Comments
https://wiki.vnoi.info/translate/he/Number-Theory-7
finally...
Finally!!! :)))