#P1008. 文件夹拆分

文件夹拆分

题目背景

电脑课上,老师给了一个装有 nn 个文件的文件夹。为了整理资料,可以把一个文件夹拆成两个小文件夹,但两个小文件夹中的文件数量差必须正好为 kk

题目描述

如果一个文件夹里有 mm 个文件,并且存在两个正整数 a,ba,b 满足:

  • a+b=ma+b=m
  • a>0a>0b>0b>0
  • aabb 的差为 kk

那么这个文件夹就可以拆成大小为 aabb 的两个文件夹。拆出的文件夹还可以继续按同样规则拆分。

一直拆到所有文件夹都无法继续拆分为止。请问最后一共有多少个文件夹。

输入格式

输入一行两个整数 nnkk

输出格式

输出一个整数,表示最终文件夹数量。

样例

6 2
3

提示

样例解释

66 可以拆成 2244,其中 44 又可以拆成 1133,最后共有 2,1,32,1,3 三个文件夹。

数据范围

  • 1n1091 \le n \le 10^9
  • 1k10001 \le k \le 1000