#P7200. [COCI2019-2020#1] Lutrija

    ID: 5811 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>2019Special Judge深度优先搜索,DFS素数判断,质数,筛法COCI

[COCI2019-2020#1] Lutrija

题目背景

Vedran 在赌输彩票之后,无意之间打开了 COCI 的频道。只要完成 COCI 给出的任务,他就能够免除前往新加坡 IOI2020 现场的费用。

不幸的是,Vedran 已经老了,于是你决定帮帮他。

题目描述

给定两个素数 A,BA,B。你需要给出一个开头和结尾分别为 AABB 的序列,使得其所有元素均为素数,并且相邻两个元素之间的差值也为素数。

输入格式

输入两个素数 A,BA,B

输出格式

如果任务不可能完成,即没有满足条件的序列(以下称为有解),则只输出 -1

否则,在第一行输出序列的元素个数,并在第二行输出所有元素。

如果有解,则你的构造必须满足下列二者之一:

  • 序列元素个数不超过 3030
  • 任何一个元素都不超过 101510^{15}

如果有多组解,则输出任意一种。

13 11
2
13 11
37 11
-1
2 17
3
2 19 17

提示

数据规模及约定

对于 20%20\% 的数据,如果有解,则必定有一种解,满足元素的个数不超过 33,且其中的所有元素都不超过 10001000

对于另外 40%40\% 的数据,2A,B10002 \le A,B \le 1000

对于 100%100\% 的数据,2A,B1014,AB2 \le A,B \le 10^{14},A \neq B

说明

本题分值按 COCI 原题设置,满分 7070

由于平均下来每个测试点为 2.52.5 分,因而将其中一半的测试点设置为 22 分,另一半设置为 33 分。

本题使用非官方的 Special Judge,欢迎大家 hack(可私信或直接发帖)。

题目译自 COCI2019-2020 CONTEST #1 T2 Lutrija