← 返回题目列表

AtCoder · abc279_h

Ex. 最小值乘积之和

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你正整数 N 和 M。在此,可以保证 N\leq M \leq 2N.

打印总和,模数 200\ 003 (素数),在所有正整数序列上具有以下值 S=(S_1,S_2,\dots,S_N) 这样 \displaystyle \sum_{i=1}^{N} S_i = M (注意不寻常的模数):

  • \displaystyle \prod_{k=1}^{N} \min(k,S_k).

约束

  • 1 \leq N \leq 10^{12}
  • N \leq M \leq 2N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M

输出

将答案打印为整数。


示例输入 1

3 5

示例输出 1

14

有六个序列 S 满足条件: S=(1,1,3), S=(1,2,2), S=(1,3,1), S=(2,1,2), S=(2,2,1), S=(3,1,1).

值 \displaystyle \prod_{k=1}^{N} \min(k,S_k) 对于其中每一个 S 如下。

  • S=(1,1,3) : 1\times 1 \times 3 = 3
  • S=(1,2,2) : 1\times 2 \times 2 = 4
  • S=(1,3,1) : 1\times 2 \times 1 = 2
  • S=(2,1,2) : 1\times 1 \times 2 = 2
  • S=(2,2,1) : 1\times 2 \times 1 = 2
  • S=(3,1,1) : 1\times 1 \times 1 = 1

因此,您应该打印它们的总和: 14.


示例输入 2

1126 2022

示例输出 2

40166

打印模数之和 200\ 003.


示例输入 3

1000000000000 1500000000000

示例输出 3

180030