#1692. 大冬天题

    ID: 1692 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1046来源:qoj.ac数据:公开样例

大冬天题

大冬天题

题目描述

标题: 大冬天题 - Problem - QOJ.ac

#5091. 大冬天题

Statistics

The problem was used in the following contests:

大冬天的,djq 和 dxm 在打牌。

两人首先约定了两个正整数 n,k,满足 n 是偶数且 n≥2k。接着两人各拿到 k 张牌,dxm 手上的第 i(1≤i≤k) 张牌上写有正整数 n+(2i−1),djq 手上的第 i(1≤i≤k) 张牌上写有正整数 n−(2i−1)。可以注意到双方的牌恰好构成 2k 个连续的奇数。

接下来游戏将进行 k 轮,每轮中双方从自己剩下的手牌中各打出一张牌,打出的牌不能收回。如果两张牌上的数字互质,那么 djq 得一分,否则 dxm 得一分。所有轮次结束后,双方统计各自得分的总和,作为整场游戏的得分。

djq 已经知道,第 i 轮中,dxm 将打出自己手上的第 i 张牌。现在他想知道:

  • 他最高的可能得分;
  • 一种让他拿到可能最高分的打牌方案。

请写一个程序帮帮他吧!

输入格式

一行两个正整数 n,k。

输出格式

第一行输出一个整数 s,表示 djq 可能的最高得分。

接下来 k 行每行输出一个整数,第 i 行的整数 pi 表示 djq 应该在第 i 轮中打出的牌的编号。

输入输出样例

样例输入

10 3

样例输出

3
3
1
2

样例解释

dxm 手中的牌依次为 [11,13,15],djq 手中的牌依次为 [9,7,5]。djq 只需要以 [5,9,7] 的顺序出牌即可拿到全部 3 分。

评分方式

本题设有 Special Judge。为了保证 Special Judge 正常工作,你需要保证:

  • 输出的第一行是一个 [0,k] 的整数。
  • 接下来的 k 行每行是一个 [1,k] 的整数。
  • 输出不含其他内容。

违反上述规范可能导致不能得到任何分数。

在输出符合规范的前提下,按如下方式计分:

  • 如果 s 和输出的方案都正确,获得该测试点满分。
  • 如果 s 正确但输出的方案不正确,获得该测试点满分的 15%。
  • 否则将不会获得任何分数。

数据范围与约定

对于全部数据,1≤k≤106,2k≤n≤10100,保证 n 是偶数。

本题设有若干个子任务。对于每个子任务,你的得分是其中每个测试点得分的最小值。

子任务编号 k n 分值 1 ≤10 ≤109 5 2 ≤20 5 3 ≤200 15 4 ≤2×103 10 5 n=2k 25 6 ≤105 ≤109 10 7 15 8 15

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

10 3
3
3
1
2