#P13569. [ICPC 2022 Yokohama R] Cake Decoration

    ID: 12769 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-对称性去重固定一个变量消去另一维枚举较小维度向下取整与向上取整二分查找

[ICPC 2022 Yokohama R] Cake Decoration

题目描述

你正在订购一个蛋糕来庆祝新年。你需要确定装饰物品在蛋糕上的数量。可用的物品有狗雕像、猫雕像、红色糖果和蓝色糖果。

你希望用这四种物品装饰蛋糕,并且这四种物品的数量彼此不同。你还希望雕像(狗和猫的总数)的数量在某个范围内。

装饰物品的额外费用会加到蛋糕的价格中。额外费用虽然相当奇怪,但却是四种装饰物品数量的乘积。你希望在预算允许的情况下,让蛋糕看起来尽可能华丽。因此,如果你可以在不违反预算限制的情况下增加四种物品中的任意一种,那么你对这种装饰方案就不满意。

上述条件总结如下:设 dd、cc、rr 和 bb 分别表示狗雕像、猫雕像、红色糖果和蓝色糖果的数量。所有这些数量应是不同的正整数,并满足给定的 XX、LL 和 RR 的以下条件:

  • L≤d+c<RL \leq d + c < R,
  • d×c×r×b≤Xd \times c \times r \times b \leq X,
  • (d+1)×c×r×b>X(d+1) \times c \times r \times b > X,
  • d×(c+1)×r×b>Xd \times (c+1) \times r \times b > X,
  • d×c×(r+1)×b>Xd \times c \times (r+1) \times b > X,以及
  • d×c×r×(b+1)>Xd \times c \times r \times (b+1) > X。

可能有多种装饰物品数量的组合满足这些条件。你的任务是找出有多少种这样的组合存在。

输入格式

输入由单个测试用例组成,格式如下。

X L RX \ L \ R

这里,XX、LL 和 RR 是上述条件中出现的整数。它们满足 1≤X≤10141 \leq X \leq 10^{14} 和 1≤L<R≤10141 \leq L < R \leq 10^{14}。

输出格式

输出满足上述条件的装饰物品数量组合的数量,结果对质数 998244353=223×7×17+1998244353 = 2^{23} \times 7 \times 17 + 1 取模。

输入输出样例 #1

输入 #1

24 4 6

输出 #1

12

输入输出样例 #2

输入 #2

30 5 6

输出 #2

4

输入输出样例 #3

输入 #3

30 9 20

输出 #3

0

输入输出样例 #4

输入 #4

100000000000000 1 100000000000000

输出 #4

288287412

说明/提示

对于样例输入 2,四种组合 (d,c,r,b)=(2,3,1,5)(d, c, r, b) = (2,3,1,5)、(2,3,5,1)(2,3,5,1)、(3,2,1,5)(3,2,1,5) 和 (3,2,5,1)(3,2,5,1) 满足所有条件。(d,c,r,b)=(1,4,2,3)(d, c, r, b) = (1,4,2,3) 不符合条件,因为即使再增加一只猫雕像,其装饰物品的额外费用也没有超过 X=30X = 30。(d,c,r,b)=(1,5,2,3)(d, c, r, b) = (1,5,2,3) 也不符合条件,因为 d+c<R=6d + c < R = 6 不成立。