問題一覧 > 通常問題

No.2940 Sigma Sigma Div Floor Problem

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 92
作問者 : kazuppa / テスター : highlighter Magentor hirayuu_yc
3 ProblemId : 11225 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-01-22 18:20:44

問題文

ある正整数 NN が与えられます。

(∑i=1N∑j=1i⌊ij⌋) mod 998244353\left(\displaystyle\sum_{i=1}^N\displaystyle\sum_{j=1}^i\left\lfloor \dfrac{i}{j}\right\rfloor \right)\bmod{998244353} を求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
NN

制約

  • 1≤N<1.2×1061\leq N< 1.2 \times 10^6
  • NN は整数
また、この問題にはAC判定とは関係のないevilケースが用意されています。余力のある人は挑戦してみてください。

evilケースの制約
  • 1≤N≤10151\leq N\leq 10^{15}
  • NN は整数
なお、evilケースに挑戦しない人は、入力が通常制約に満たさなかった場合に即座にプログラムを終了していただけると、ジャッジが早く終了します。

出力

1行に式の答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
2
出力
4

⌊11⌋=1,⌊21⌋=2,⌊22⌋=1\left\lfloor \dfrac{1}{1} \right\rfloor =1,\left\lfloor \dfrac{2}{1} \right\rfloor =2,\left\lfloor \dfrac{2}{2} \right\rfloor =1 なので、答えは 1+2+11+2+1 で 44 となります。

サンプル2
入力
5
出力
27

サンプル3
入力
100
出力
21803

サンプル4
入力
14691
出力
32934

答えを 998244353998244353 で割ることに注意して下さい。

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