#1965. 操作序列计数

    ID: 1965 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest313来源:qoj.ac数据:公开样例动态规划

操作序列计数

操作序列计数

题目描述

标题: 操作序列计数 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

有个变量 i ,初始 i=1 。

现在有两种操作:

  1. i=i+1 ;
  2. i=i×k 。

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

输入格式

第一行一个整数 k 。

第二行一个整数 n 。

输出格式

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

样例数据

样例输入

5
12

样例输出

12
11

子任务

对于所有数据,2≤k≤10,1≤n≤k50。

  • 子任务 1(3 分):n≤106;
  • 子任务 2(10 分):k=2,n≤109;
  • 子任务 3(20 分):k=2;
  • 子任务 4(20 分):n≤109;
  • 子任务 5(20 分):n≤1018;
  • 子任务 6(27 分):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
12
12
11