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

→ Pay attention

Before contest
Refact.ai Match 1 (Codeforces Round 985)
3 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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)