問題一覧 > 通常問題

No.1781 LCM

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : testestesttestestest
2 ProblemId : 7317 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-25 23:44:05

問題文

正整数 $N,M$ が与えられます。
各要素が正整数である長さ $N$ の数列 $A$ 全てについての $\displaystyle \left\lfloor \frac{M}{{\rm lcm}(A)}\right\rfloor$ の和を $998244353$ で割った余りを求めてください。
ただし、${\rm lcm}(A)$ は $A$ の要素全てを約数に持つような最小の正整数とします。

入力

$N$ $M$

$1\leq N \leq 10^{11}$
$1\leq M \leq 10^{11}$

テストケースは32個ある。うち、16個は $N,M \leq 2\times 10^5$ を満たす。(★3くらい)

出力

答えを出力してください。

サンプル

サンプル1
入力
3 2
出力
9

$\displaystyle \left\lfloor \frac{M}{{\rm lcm}(A)}\right\rfloor$ が $1$ になる数列が $7$ 個、$2$ になる数列が $1$ 個あります。

サンプル2
入力
3 4
出力
44

$\displaystyle \left\lfloor \frac{M}{{\rm lcm}(A)}\right\rfloor$ が $1$ になる数列が $26$ 個、$2$ になる数列が $7$ 個、$4$ になる数列が $1$ 個あります。

サンプル3
入力
200000 200000
出力
68905

$998244353$ で割った余りを求めてください。

サンプル4
入力
100000000000 100000000000
出力
369470795

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。