题目背景
译自 COCI 2024/2025 #5 T3。2s,0.5G。满分为 90。
题目描述
给定正整数序列 h1,…,hn。
对于区间 [l,r],我们称 i(l≤i≤r)关于 [l,r] 是好的,当且仅当:hi=gcd(hl,hl+1,…,hr)。
对于 i,定义 f(i) 表示:所有 i 关于 [l,r] 是好的区间中,r−l+1 的最大值。
对于 i=1,2,…,n,求出 f(i)。
输入格式
第一行,正整数 n。
第二行,n 个正整数 h1,h2,…,hn。
输出格式
输出 n 个正整数 f(1),f(2),…,f(n)。
6
3 6 6 6 1 3
4 3 3 3 6 1
5
10 2 10 15 5
1 3 1 1 3
提示
数据范围
对于 100% 的数据,保证 1≤n,hi≤106。
子任务编号 |
n≤ |
特殊性质 |
得分 |
1 |
100 |
|
7 |
2 |
5×103 |
11 |
3 |
5×104 |
17 |
4 |
106 |
A |
29 |
5 |
|
26 |
特殊性质 A:hi≤100。