????count increasing subsequence in O(n)

→ Pay attention

Before contest
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

View all →

→ Find user

→ Recent actions

Detailed →

????count increasing subsequence in O(n)

Difference between en2 and en3, changed 4 character(s)

So the question is count the number of increasing subsequence such that the gcd of subsequence will be equal to 1.↵
↵
1 <= size of array <= 1e5↵
1 <= a[i] <= 1e6↵
↵
can anyone help me solve this problem.

History

Revisions

Rev.	By	When	Δ	Comment
en4	i_am_not_special	2024-08-08 17:19:56	19
en3	i_am_not_special	2024-08-08 10:38:39	4
en2	i_am_not_special	2024-08-08 10:35:06	2
en1	i_am_not_special	2024-08-08 10:30:34	239	Initial revision (published)