You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

完全K叉树的直径

题目背景

我们都知道一棵深度为 $k$ 且有 $2^k-1$ 个结点的二叉树是满二叉树（即除了最下面一层以外每个结点都有 $2$ 个儿子），如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左而右，那么一棵深度为 $k$ ，有 $n$ 个结点的二叉树被称为完全二叉树，当且仅当其每一个结点都与深度为 $k$ 的满二叉树中编号从 $1$ 至 $n$ 的结点一一对应时, 称之为完全二叉树。

类似地，我们定义满 $k$ 叉树为除了最下面一层以外每个结点都有 $k$ 个儿子的树，完全 $k$ 叉树为每一个结点都与深度为 $k$ 的满 $k$ 叉树中编号从 $1$ 至 $n$ 的结点一一对应的树。

而树的直径的定义是树上两个结点之间的最长距离。

接下来的问题就和完全 $k$ 叉树的直径有关。

题目描述

求一棵具有 $n$ 个顶点的完全 $k$ 叉树的直径长度和直径数量。

输入格式

一行两个用空格分隔开的整数 $n, k$ 。

输出格式

两行，第一行一个整数表示这棵树的直径长度，第二行一个整数表示这棵树的直径条数。

样例 #1

样例输入 #1

5 2

样例输出 #1

3
2

样例 #2

样例输入 #2

10 3

样例输出 #2

4
9

提示

数据范围

本题共 $20$ 个测试点，每个测试点 $5$ 分，满分 $100$ 。

对所有测试点，满足 $2\le n\le 5\times 10^6,2\le k\le 500$ 。

特殊性质：保证这棵树是一棵满 $k$ 叉树。