F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

数论

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 116    Accepted Submission(s): 42


Problem Description
给定长度为 $n$ 的正整数数列 $a_1,a_2,\dots,a_n$ 。

定义不交区间集为若干**不交**的区间$[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$的集合,其中任意集合 $[l_i,r_i]$ 满足 $1\le l_i\le r_i\le n$。

我们称两个不交区间集不同,当且仅当这两个区间的集合不同。

我们称一个不交区间集是**好的**,当且仅当

$\mathop{\text{gcd}}\limits_{i\in [l_1,r_1]}\{a_i\} = \mathop{\text{gcd}}\limits_{i\in [l_2,r_2]}\{ a_i\} = \cdots = \mathop{\text{gcd}}\limits_{i\in [l_k,r_k]}\{a_i\}$

请你对每个 $a_i$ 求出,有多少个**好的不交区间集**,会将其选入在某一个区间中。
 

Input
第一行一个整数 $n\ (1 \leq n\leq 10^5)$,代表数列的长度。

第二行 $n$ 个整数,$a_1,a_2,\dots,a_n\ (1 \leq a_i \leq 10^9)$。
 

Output
输出一行 $n$ 个整数,第 $i$ 个数表示有几个**好的不交区间集**,会将 $a_i$ 选入在某一个区间中。

由于答案很大,输出的数字对 $998244353$ 取模。
 

Sample Input
6 3 6 12 2 4 1
 

Sample Output
9 13 15 15 12 9
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-10 12:29:12, Gzip enabled