Записи в блоге

Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

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

До соревнования
Codeforces Round 1133 (Div. 1)
15:01:37
Зарегистрироваться »

*есть доп. регистрация

До соревнования
Codeforces Round 1133 (Div. 2)
15:01:38
Зарегистрироваться »

*есть доп. регистрация

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

№	Пользователь	Рейтинг
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

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

Всё →

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

№	Пользователь	Вклад
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

Всё →

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

→ Прямой эфир

Детальнее →

Блог пользователя xINFERNOx

Time Complexity Variation

Автор xINFERNOx, история, 5 лет назад, По-английски

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

-7

xINFERNOx
5 лет назад
3

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

Время на сервере: 07.11.2026 02:33:23 (g2).

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

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