Time Complexity Variation

→ Pay attention

Before contest
Codeforces Round 998 (Div. 3)
11:16:12
Register now »

→ Streams

Codeforces Round 998 (Div 3) — Solution Discussion

By Shayan

Before stream 13:51:12

Codeforces Round 998 Solution Discussion

By aryanc403

Before stream 13:56:12

View all →

→ Top rated

#	User	Rating
1	jiangly	3976
2	tourist	3815
3	jqdai0815	3682
4	ksun48	3614
5	orzdevinwang	3526
6	ecnerwala	3514
7	Benq	3482
8	hos.lyric	3382
9	gamegame	3374
10	heuristica	3357

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	168
2	-is-this-fft-	165
3	Um_nik	161
4	atcoder_official	160
5	djm03178	157
6	Dominater069	156
7	adamant	154
8	luogu_official	152
9	awoo	151
10	TheScrasse	147

View all →

→ Find user

→ Recent actions

Detailed →

Time Complexity Variation

Revision en1, by xINFERNOx, 2021-12-17 22:40:08

Why the second code executes within 500ms whereas the first one gives TLE(2000ms) ?

1497E1 - Square-Free Division (easy version)

const int N = 1e7 + 5;
vector<int> maping(N);
int i,j;

Code 1

for (i = 1; i < N; i++) {
	maping[i] = i;
}
for (i = 2; i < N; i++) {
  for (j = 2; j * j <= i; j++) {
	 while (maping[i] % (j * j) == 0) maping[i] = maping[i] / (j * j);
	}
}

Code 2

for (i = 1 ; i < N ; i++) maping[i]  = i;
for (i = 2; i < N; i++) {
	for (j = i * i; j <= N; j += i * i) {
		while (maping[j] % (i * i) == 0) {
			maping[j] = maping[j] / (i * i);
		}
	}
}

number theory, sieve of eratosthenes, #sieve, doubt

History

Revisions

	Rev.	Lang.	By	When	Δ	Comment
	en1		xINFERNOx	2021-12-17 22:40:08	709	Initial revision (published)