Участник:Muradyan Armen/FRQPRIME

Материал из DISCOPAL
< Участник:Muradyan Armen
Версия от 16:18, 8 декабря 2020; Muradyan Armen (обсуждение | вклад) (Новая страница: «C++ (gcc 8.3) https://www.spoj.com/problems/FRQPRIME/ <code-cpp> #include <iostream> using namespace std; const int me = 200025; int t, n, k; int pr[me]; i…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

C++ (gcc 8.3)

https://www.spoj.com/problems/FRQPRIME/

 
#include <iostream>
 
using namespace std;
 
const int me = 200025;
 
int t, n, k;
int pr[me];
 
int main() {
 
    fill(pr + 2, pr + me, 1);
    for(int i = 2; i < me; i ++)
        if(pr[i])
            for(int j = i + i; j < me; j += i)
                pr[j] = 0;
    scanf("%d", &t);
    while(t --){
        scanf("%d%d", &n, &k);
        if(k == 0){
            cout << 1LL * n * (n - 1) / 2 << "\n";
            continue;
        }
        int s = 0, ptr = 1;
        long long ans = 0;
        for(int i = 2; i <= n; i ++){
            while(ptr < n && s < k){
                ++ptr;
                s += pr[ptr];
            }
            if(s >= k)
                ans += n - ptr + 1;
            s -= pr[i];
        }
        cout << ans << "\n";
    }
 
    return 0;
}