Time Complexity Variation

→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
28:35:21
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 30:45:19

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Time Complexity Variation

Правка en1, от 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

История

Правки

	Rev.	Язык	Кто	Когда	Δ	Комментарий
	en1		xINFERNOx	2021-12-17 22:40:08	709	Initial revision (published)

Соревнования по программированию 2.0

Время на сервере: 23.12.2024 12:59:41 (l1).

Десктопная версия, переключиться на мобильную.

При поддержке