#3074. 「2019 集训队互测 Day 3」操作序列计数

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: kczno1

题目描述

有个变量 i ,初始 i=1

现在有两种操作:

  1. i=i+1
  2. i=i \times k

给定 n,k ,对于所有可能的 L ,问有多少种操作序列,满足操作 2 的个数为 L ,且依次执行所有操作后, i \le n

输入格式

第一行一个整数 k

第二行一个整数 n

输出格式

对于所有可能的 L ,按 L 从小到大的顺序,每行输出一个答案。

样例

样例输入

5
12

样例输出

12
11

数据范围与提示

对于所有数据, 2 \le k \le 10 1 \le n \le k^{50}

  • 子任务 1 3 分): n \le 10^6
  • 子任务 2 10 分): k=2 n\le 10^9
  • 子任务 3 20 分): k=2
  • 子任务 4 20 分): n \le 10^9
  • 子任务 5 20 分): n \le 10^{18}
  • 子任务 6 27 分):无特殊限制。