该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P5425 [USACO19OPEN] I Would Walk 500 Miles G

题目描述

Farmer John 想要将他的编号为 $1 \ldots N$ 的 $N$ 头奶牛（ $N \leq 7500$ ）分为非空的 $K$ 组（ $2 \leq K \leq N$ ），使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛 $x$ 和奶牛 $y$ （其中 $1 \leq x<y \leq N$ ）愿意为了见面走 $(2019201913x+2019201949y) \mod 2019201997$ 英里。

给定一个将 $N$ 头奶牛分为 $K$ 个非空小组的分组方案，令 $M$ 为任意两头来自不同组的奶牛愿意为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度，Farmer John 想要将 $N$ 头奶牛以最佳的方式分为 $K$ 组，使得 $M$ 尽可能大。

输入格式

输入仅有一行，包含 $N$ 和 $K$ ，用空格分隔。

输出格式

输出最优的 $M$ 。

输入输出样例 #1

输入 #1

3 2

输出 #1

2019201769

说明/提示

在这个例子中，奶牛 $1$ 和奶牛 $2$ 愿意为了见面走 $2019201817$ 英里。奶牛 $2$ 和奶牛 $3$ 愿意走 $2019201685$ 英里。奶牛 $1$ 和奶牛 $3$ 愿意走 $2019201769$ 英里。所以，将奶牛 $1$ 单独分为一组，奶牛 $2$ 和奶牛 $3$ 分为一组，$M = \min(2019201817, 2019201769) = 2019201769$（这是我们在这个问题中能够达到的最佳结果）。