AdditionalFile4840.zip

P9407 [POI 2020/2021 R3] 素数和 / Suma liczb pierwszych

题目背景

译自 XXVIII Olimpiada Informatyczna - III etap Suma liczb pierwszych。

d2t3。

题目描述

给你一个数字 $n$，求 $l,r$，使 $[l,r]$ 区间内的所有质数之和等于 $n$。

如果有多解，任意一组均可；无解输出 NIE。

输入格式

一行一个正整数 $n$。

输出格式

如果有解，一行两个正整数 $l,r$，其中要求 $1 \le l \le r \le n$，表示你的答案。

如果无解，输出 NIE。

输入输出样例 #1

输入 #1

15

输出 #1

3 7

输入输出样例 #2

输入 #2

9992

输出 #2

4993 4999

输入输出样例 #3

输入 #3

100000000

输出 #3

NIE

输入输出样例 #4

输入 #4

1000000007

输出 #4

1000000007 1000000007

输入输出样例 #5

输入 #5

99999999996

输出 #5

295693 1693067

说明/提示

对于所有数据，$1\leq n\leq 10^{11}$。

子任务编号	附加限制	分数
1	$n\leq 10000$	15
2	$n\leq 10^8$	20
3	$n\leq 2\times 10^9$	40
4	$n\leq 10^{11}$	25

#4840. 「POI 2020/2021 R3」Suma liczb pierwszych

标签: 传统 | 时间限制: 15000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Suma liczb pierwszych

如果一个自然数 $n$ 恰好只有两个不同的因数 $1$ 和 $n$，我们就称它为质数。例如，$6$ 不是质数（因为它能被 $2$ 整除），$1$ 也不是质数（因为它只有一个因数 $1$），但 $2$ 和 $7$ 是质数。

Bajtazar 特别喜欢质数。他在一张纸上写下了连续的质数序列：

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \ldots$$

他想从这个序列中挑选出一个连续的片段，使其和恰好等于他喜欢的数字 $N$。请你帮助他，编写一个程序，对于给定的数字 $N$，找出质数序列中一个连续的区间，使其和恰好等于 $N$。

输入格式

输入只有一行，包含一个自然数 $N$ $(1 \leq N \leq 10^{11})$，表示 Bajtazar 期望的和。

输出格式

输出只有一行，包含两个质数 $L$ 和 $R$ $(1 \leq L \leq R \leq N)$，表示质数序列中闭区间 $[L, R]$ 内的数字之和恰好等于 $N$。

如果存在多种解法，你的程序可以输出任意一种。如果解不存在，则应输出 NIE。

样例 1

输入

15

输出

3 7

样例 2

见附加文件下 [sum1.in](file:sum1.in) 和 [sum1.out](file:sum1.out)。

该样例满足 $N=9992$，答案是 $[4993, 4999]$；

样例 3

见附加文件下 [sum2.in](file:sum2.in) 和 [sum2.out](file:sum2.out)。

该样例满足 $N=10^{8}$，答案是 NIE；

样例 4

见附加文件下 [sum3.in](file:sum3.in) 和 [sum3.out](file:sum3.out)。

该样例满足 $N=10^{9}+7$，答案是 $\left[10^{9}+7, 10^{9}+7\right]$；

样例 5

见附加文件下 [sum4.in](file:sum4.in) 和 [sum4.out](file:sum4.out)。

该样例满足 $N=10^{11}-4$，答案是 $[295693, 1693067]$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$N \leq 10000$	$15$
$2$	$N \leq 10^{8}$	$20$
$3$	$N \leq 2 \cdot 10^{9}$	$40$
$4$	无附加限制	$25$