#P2505. tickets

    ID: 1560 传统题 1000ms 128MiB 尝试: 60 已通过: 36 难度: 8 上传者: 标签>CF2400提高+/省选-数位 DP预计算转移分治算法2011福建集训

tickets

题目描述

有一位售票员给乘客售票,对于每位乘客,他会卖出多张连续的票,直到已卖出的编号的所有位置上的数的和不小于给定的正数 kk 。然后他会按照相同的规则给下一位乘客售票。初始时,售票员持有的编号是从 LL 到 RR 的连续整数。请你求出,售票员可以售票给多少位乘客。

输入格式

三个整数 L,R,kL,R,k

输出格式

一个正整数,表示能够拿到票的乘客数

40 218 57
29

数据规模与约定

数据范围: 1≤L≤R<=1018,1≤k≤10001\le L \le R<=10^{18} ,1 \le k \le 1000 。

题目来源

2011福建集训