No.1781 LCM
testestest問題文
正整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。