#B. 东东的奶牛

    Type: Default 1000ms 256MiB

东东的奶牛

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.

题目描述

东东的奶牛对探索农场周围的领地产生了兴趣。最初,所有 NN 头奶牛(1N1091 \leq N \leq 10^9)以一个大群体的形式开始沿着一条道路旅行。当遇到岔路时,群体有时会选择分成两个较小的(非空)群体,每个群体沿着一条道路继续前进。当其中一个群体到达另一个岔路时,它可能会再次分裂,依此类推。

奶牛们设计了一种特殊的分裂方式:如果它们可以分裂成两个群体,使得群体的大小正好相差 KK1K10001 \leq K \leq 1000),那么它们就会以这种方式分裂;否则,它们就停止探索,开始安静地吃草。

假设总是会有新的岔路,计算最终安静吃草的奶牛群的数量。

输入格式

两个空格分隔的整数,NNKK

输出格式

一个整数,表示安静吃草的奶牛群的数量。

输入输出样例 #1

6 2
3

66 头奶牛,群体大小的差异是 22

最终有 33 个群体(分别有 221133 头奶牛)。

  6
 / \
2   4
   / \
  1   3

数据范围

80% n106n \le 10^6

100% 1n109,1k10001 \le n \le 10^9, 1 \le k \le 1000

初一第一场

Not Attended
Status
Done
Rule
IOI
Problem
6
Start at
2025-9-5 10:45
End at
2025-9-5 12:45
Duration
2 hour(s)
Host
Partic.
8