問題一覧 > 通常問題

No.2318 Phys Bone Maker

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 90
作問者 : 👑 amentorimaruamentorimaru / テスター : tatyamtatyam cleanttedcleantted
6 ProblemId : 9244 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-26 12:49:23

問題文

仮想空間のアバターのエトワーニュくんは自分のしっぽの設定をして先端であるほどよく揺れるようにしようとしています。かわいいですね。


エトワーニュくんが任意の正整数列 $A = (A_1, A_2, \dots , A_M)$ を入力すると、しっぽの $M+1$ 箇所に揺れの大きさを表す整数 $X_0, X_1, \dots, X_M$ が以下のようにして割り当てられます。
（ここで、数列の長さ $M$ もエトワーニュくんが選ぶことができることに注意せよ。）

  • $X_0 = 1$
  • $X_i = \text{LCM}(X_{i-1},A_i)$ （ $\text{LCM}(a, b)$ は $a$ と $b$ の最小公倍数を表す。）

正の整数 $N$ が与えられます。エトワーニュくんは次の条件を満たすしっぽを作りたいです。

  • $1=X_0 \ < \ X_1 \ < \ \dots < \ X_M = N$

この条件を満たす正整数列 $A$ はいくつありますか？ただし、答えは非常に大きくなることがあるので、答えを $998244353$ で割った余りを求めてください。

入力

$N$
  • 入力はすべて整数
  • $2 \le N \le 10^{12}$

出力

条件を満たす正整数列 $A$ の個数を $998244353$ で割った余りを出力せよ。

サンプル

サンプル1
入力
6
出力
5

条件を満たす正整数列 $A$ は次の $5$ つです。

$A = (6) , (2,3) , (2,6) ,(3,2),(3,6)$


例えば $A=(3,6)$ の場合、$X$ は下記のようになり条件を満たします。

  • $X_0=1$
  • $X_1=\text{LCM}(X_0,A_1)=3$
  • $X_2=\text{LCM}(X_1,A_2)=6=N$

$A=(6,3)$ の場合 $X=(1,6,6)$ となり、 $X_1 < X_2$ を満たしません。

$A=(3,4)$ の場合 $X=(1,3,12)$ となり、 $X_2 = N$ を満たしません。

サンプル2
入力
8
出力
4

サンプル3
入力
963761198400
出力
55988508

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

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