問題一覧 > 通常問題

No.3106 Simple Math Problem 3

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : shobonvip / テスター : noya2
1 ProblemId : 11563 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-11 21:20:43

問題文

正整数 $N$ が与えられます。正整数 $A, B$ の組であって、次の $2$ つの条件をともに満たすものに対する $A \bmod B$ の値の総和を $998244353$ で割った余りを求めてください。

  • $1 \le A \le N$
  • $B \times (A \bmod B) < A$

ただし、 $A \bmod B$ とは $A$ を $B$ で割った余りの値（ $0$ 以上 $B$ 未満）を表します。

制約

  • $1 \le N \le 10^{12}$
  • $N$ は整数である

入力

$N$

出力

答えを出力せよ。

サンプル

サンプル1
入力
5
出力
4

条件を満たす $(A, B)$ の組は以下の $14$ 個です。

  • $(A,B) = (1,1)$ … $A \bmod B = 0$
  • $(A,B) = (2,1)$ … $A \bmod B = 0$
  • $(A,B) = (2,2)$ … $A \bmod B = 0$
  • $(A,B) = (3,1)$ … $A \bmod B = 0$
  • $(A,B) = (3,2)$ … $A \bmod B = 1$
  • $(A,B) = (3,3)$ … $A \bmod B = 0$
  • $(A,B) = (4,1)$ … $A \bmod B = 0$
  • $(A,B) = (4,2)$ … $A \bmod B = 0$
  • $(A,B) = (4,3)$ … $A \bmod B = 1$
  • $(A,B) = (4,4)$ … $A \bmod B = 0$
  • $(A,B) = (5,1)$ … $A \bmod B = 0$
  • $(A,B) = (5,2)$ … $A \bmod B = 1$
  • $(A,B) = (5,4)$ … $A \bmod B = 1$
  • $(A,B) = (5,5)$ … $A \bmod B = 0$

これらの $A \bmod B$ の総和は $4$ になるので、 $4$ を出力します。

サンプル2
入力
2
出力
0

サンプル3
入力
2025
出力
1005189

サンプル4
入力
314159265358
出力
783124332

$A \bmod B$ の総和は $24673971873667135333427$ になりますが、これを $998244353$ で割った余りである $783124332$ を出力します。

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