Skip to content

S2OJ - 911. Prime

题解504 字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

众所周知,我们称一个大于一的整数 xx 为质数,当且仅当:

i[2,x1], ix\forall i \in [2, x - 1], \, i \nmid x

小 C 认为这个定义不够优美,于是他定义了类质数,他会给出一个常数 KK,一个数 xx 为质数,当且仅当:

i[2,min(x1,K)], ix\forall i \in [2, \min(x - 1, K)], \, i \nmid x

给出 L,R,KL, R, K,求在 [L,R][L, R] 之内所有类质数的异或和。

#输入格式

一行三个整数 L,R,KL, R, K

#输出格式

一行一个整数表示答案。

#输入输出样例

样例输入 #1

2 16 2

样例输出 #1

3

样例解释 #1

[2,16][2, 16] 中的类质数有:2,3,5,7,9,11,13,152, 3, 5, 7, 9, 11, 13, 15

样例输入 #2

100 1000 2333333

样例输出 #2

561

样例输入 #3

10000000000 10000001000 423

样例输出 #3

170

#数据范围与约定

对于 100%100\% 的数据,有 2LR10142 \leq L \leq R \leq 10^{14}1K1091 \leq K \leq 10^90RL1070 \leq R - L \leq 10^7

#思路

对于 [1,min(R,k)][1, \min(\sqrt{R}, k)] 之间的每个质数 pp,将其在 max(L,2p)\max(L, 2p) 之间的倍数标记,最后没有被标记过的就是类质数。

#代码

C++
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
#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e7 + 5;

long long l, r, k, ans;
int cnt, primes[N];
bool vis[N];

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> l >> r >> k;

for (long long i = 2; i * i <= r && i <= k; i++) {
for (long long j = std::max(((l + i - 1) / i) * i, i * 2); j <= r; j += i) {
vis[j - l + 1] = true;
}
}

for (long long i = l; i <= r; i++) {
if (!vis[i - l + 1]) ans ^= i;
}

cout << ans << endl;

return 0;
}