A7980.奶牛分群

普及-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

约翰的 NN 只奶牛要出发去探索牧场四周的土地。它们将沿着一条路走,一直走到三岔路口(可以认为所有的路口都是这样的)。这时候,这一群奶牛可能会分成两群,分别沿着接下来的两条路继续走。如果她们再次走到三岔路口,那么仍有可能继续分裂成两群继续走。

奶牛的分裂方式十分古怪:

如果这一群奶牛可以精确地分成两部分,这两部分的牛数恰好相差 KK 头,那么在三岔路口牛群就会分裂。

否则,牛群不会分裂,她们都将在这里待下去,平静地吃草。 请计算,最终将会有多少群奶牛在平静地吃草。

输入格式

两个整数 N,K(1N1e9,1K1e3)N,K(1 \leq N \leq 1e9,1 \leq K \leq 1e3)

输出格式

输出一个整数,表示最终将会有多少群奶牛在平静地吃草。

输入输出样例

  • 输入#1

    6 2

    输出#1

    3

【普及组算法4】递归

0/15
首页