Need Help - Codeforces

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

До соревнования
Codeforces Round (Div. 2)
7 дней

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

№	Пользователь	Рейтинг
1	Benq	3676
2	jiangly	3670
3	Kevin114514	3657
4	maroonrk	3355
5	Um_nik	3353
6	squareOf105	3346
7	tourist	3343
8	strapple	3324
9	heuristica	3322
10	jiangbowen	3291

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

Всё →

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

№	Пользователь	Вклад
1	Qingyu	158
2	nik_exists	150
2	maspy	150
4	AmShZ	143
4	Um_nik	143
6	Errichto	139
7	adamant	137
8	BledDest	134
9	maroonrk	133
10	qwexd	130

Всё →

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

→ Прямой эфир

Детальнее →

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

Need Help

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

I need help to solve this problem.

Thanks in advance.

Happy Coding :)

#number theory

kratos99
6 лет назад
3

Комментарии (3)

Написать комментарий?

dapingguo8

6 лет назад, скрыть # |

← Rev. 5 →

1.Use Linear Sieve to take primes no more than $$$n$$$ out, store them.

Linear Sieve

vector<int>pr;
bool p[500000005];//this array consumes ~500MB of space. The Memory limit is 1024MB, so it's enough.
void primes(){
    for(int i=2;i<=n;i++){
        if(!p[i])pr.push_back(i);
        for(int j=0;j<pr.size() and pr[j]*i<=n;j++){
            p[pr[j]*i]=true;
            if(i%pr[j]==0){
                break;
            }
        }
    }
}

2.Use upper_bound() to find the position of the smallest prime strictly greater than $$$n$$$. Then we can calculate $$$\pi(n)$$$ easily.

3.$$$\forall i: i\ge 0 $$$ and $$$ p_{A\times i+B} \le n$$$, store $$$p_{A\times i+B}$$$ for answer.

4.Output what you stored for answer.

→ Ответить

kratos99

6 лет назад, скрыть # ^ |

I did this and got AC but I think purpose of problem setter is behind this question is not this so I asked.

→ Ответить

dapingguo8

6 лет назад, скрыть # ^ |

There's a time constraint of $$$10$$$ seconds, with $$$1024$$$ MB memory avaliable.

I think the purpose of the author could be that ( enumerate primes )

→ Ответить

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

Время на сервере: 17.10.2026 22:39:18 (f1).

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

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