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

Luogu
IDLGP9407
Time5000ms
Memory256MB
DifficultyP6
2020POI(波兰)Special Judge素数判断,质数,筛法双指针 two-pointer根号分治
给你一个数字 $n$,求 $l,r$,使 $[l,r]$ 区间内的所有质数之和等于 $n$。 如果有多解,任意一组均可;无解输出 `NIE`。 ## Input 一行一个正整数 $n$。 ## Output 如果有解,一行两个正整数 $l,r$,你的答案。 如果无解,输出 `NIE`。 [samples] ## Background 译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Suma liczb pierwszych](https://szkopul.edu.pl/problemset/problem/8brtPux-IyytS6rOoOR1cJTL/statement/)。 d2t3。 ## Note 对于所有数据,$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 | | 25 |
Samples
Input #1
15
Output #1
3 7
Input #2
9992
Output #2
4993 4999
Input #3
100000000
Output #3
NIE
Input #4
1000000007
Output #4
1000000007 1000000007
Input #5
99999999996
Output #5
295693 1693067
API Response (JSON)
{
  "problem": {
    "name": "[POI 2020/2021 R3] 素数和 / Suma liczb pierwszych",
    "description": {
      "content": "给你一个数字 $n$,求 $l,r$,使 $[l,r]$ 区间内的所有质数之和等于 $n$。 如果有多解,任意一组均可;无解输出 `NIE`。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9407"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给你一个数字 $n$,求 $l,r$,使 $[l,r]$ 区间内的所有质数之和等于 $n$。\n\n如果有多解,任意一组均可;无解输出 `NIE`。\n\n## Input\n\n一行一个正整数 $n$。\n\n## Output\n\n如果有解,一行两个正整数 $l,r$,你的答案。\n\n如果无解,输出 `NIE`。\n\n[samples]\n\n## Background\n\n译自 [XXVIII Olimpiada In...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments