누적합으로 구간합 구하면 된다. 대신 시작을 어디서 하냐에 따라서 결과가 두 종류로 나눠지기 때문에
홀수항에서 시작하는 배열과 짝수항에서 시작하는 배열을 만든다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <stdio.h> using namespace std; typedef long long ll; int p[100001], ind[100001], cnt, d[2][100001]; int main() { ind[2] = ++cnt; p[2] = 2; for (ll i = 3; i < 100000; i += 2) { if (p[i]) continue; p[i] = 2; ind[i] = ++cnt; for (ll j = i * i; j < 100000; j += 2 * i) p[j] = 1; } for (int i = 1, flag = 1; i <= 100000; i++) { if (!ind[i]) ind[i] = ind[i - 1]; d[0][i] = d[0][i - 1]; d[1][i] = d[1][i - 1]; if (p[i] == 2) { d[1 - flag][i] += i * 3; d[flag][i] -= i; flag = 1 - flag; } } int n, a, b, flag; scanf("%d", &n); while (n--) { scanf("%d%d", &a, &b); if (p[a] == 2) a--; flag = ind[a] % 2; printf("%d\n", d[flag][b] - d[flag][a]); } return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 2841 외계인의 기타 연주 (0) | 2018.02.17 |
|---|---|
| 3986 좋은 단어 (0) | 2018.02.17 |
| 14942 개미 (0) | 2018.02.17 |
| 15270 친구 팰린드롬 (0) | 2018.02.17 |
| 15271 친구 팰린드롬 2 (0) | 2018.02.17 |