No.1019 最小格子三角形

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 12
作問者 : maspymaspy / テスター : beetbeet
8 ProblemId : 4041 / 出題時の順位表
問題文最終更新日: 2020-04-03 03:08:07

問題文

座標平面上の、$x,y$ 座標がともに整数であるような点を格子点といいます。 $3$ 頂点が共に格子点であるような三角形の面積は、必ず $\frac12$ 以上になります。 以下、格子点からなる面積 $\frac12$ の三角形を最小格子三角形と呼びます。

牛子 さんは最小格子三角形が大好物です。 特に座標の大きなものを見つけたときに、大きな喜びを得ることができます。 牛子 さんが得られる喜びの総和を計算しましょう。

$N$ を正の整数とするとき、以下の値を計算してください。

  • $3$ 点 $O(0,0), P(p_1,p_2), Q(q_1,q_2)$ が最小格子三角形をなすとき、その喜びを、$|p_1| + |p_2| + |q_1| + |q_2|$ で定めます。
  • $OP\leqq \sqrt{N}$ かつ $OQ\leqq \sqrt{N}$ となる最小格子三角形 $OPQ$ に対する喜びの総和を、$998244353$ で割った余りを答えてください。
同じ三角形($P$, $Q$ を入れ替えただけのもの)は $1$ 度しか数えないことに注意してください。

入力

$N$

  • $N$ は正の整数で $1\leqq N\leqq 10^{12}$ を満たす。

出力

$1$ 行に、喜びの総和を $998244353$ で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
1
出力
8

例えば $P(1,0)$, $Q(0,1)$ が最小格子三角形を与えます。 この三角形からは、$2$ の喜びが得られます。 この三角形を $O$ を中心に $90$ 度ずつ回転させて得られる $4$ つの三角形が計算対象となります。

サンプル2
入力
25
出力
1208

例えば $P(4,-3)$, $Q(-3,2)$ が最小格子三角形を与えます。 この三角形からは、$12$ の喜びが得られます。

サンプル3
入力
1000000
出力
741919871

$998244353$ で割った余りを出力します。

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