Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21618. 【ExPR #1】乘积

统计

给定两个正整数 $n,m$ 。

你有一个正整数 $M$ ,初始 $M=1$ 。你将进行若干次操作,每次在 $[1,n]$ 中均匀随机选取一个整数 $x$ ,并令 $M:=M\times x$ 。当 $M>m$ 时停止操作。

求期望进行多少次操作。

可以证明,答案一定为有理数。设其为 $\frac ab$($a$ 和 $b$ 为互质的正整数,数据保证 $b$ 不为 $998244353$ 的倍数),则你需要输出一个整数 $x$ 满足 $0\le x < 998244353$ 且 $a\equiv bx \pmod{998244353}$ 。可以证明这样的 $x$ 唯一存在。

输入格式

一行,两个正整数 $n,m$ 。

输出格式

一行,一个整数 $x$ ,意义同题目描述。

样例一

input

3 2

output

748683267

explanation

答案为 $\frac 94$,$4 \times 748683267=9 \pmod {998244353}$ 。

样例二

input

2 39

output

12

样例三

input

316 12048

output

638683159

数据范围与提示

本题共 $10$ 组测试点,各 $10$ 分。

对于所有数据,$2\le n\le 9\times 10^8,1\le m\le 10^9$ 。

测试点编号 $n\le $ $m\le $
$1\sim 3$ $5000$ $5000$
$4\sim 5$ $10^6$ $10^6$
$6\sim 8$ $300$ $ $
$9\sim 10$ $ $ $ $

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$