問題一覧 > 通常問題

No.1019 Minimal Lattice Triangles

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 13
作問者 : maspy / テスター : beet
お気に入りにしたユーザー ProblemId : 4041 / 自分の提出
問題文最終更新日: 2022-04-25 10:42:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 242 (順位表) の他の問題:

Problem Statement

A point on the coordinate plane whose $x,y$ coordinates are both integers is called a lattice point. The area of a triangle whose $3$ vertices are all lattice points is always at least $\frac12$. Hereafter, a triangle of area $\frac12$ consisting of lattice points is called a minimal lattice triangle.

Ushiko loves minimal lattice triangles. In particular, she feels great joy when she finds one with large coordinates. Let us calculate the total joy that Ushiko can obtain.

Given a positive integer $N$, calculate the following value.

  • When the $3$ points $O(0,0), P(p_1,p_2), Q(q_1,q_2)$ form a minimal lattice triangle, its joy is defined as $|p_1| + |p_2| + |q_1| + |q_2|$.
  • Find the sum of the joy over all minimal lattice triangles $OPQ$ satisfying $OP\leqq \sqrt{N}$ and $OQ\leqq \sqrt{N}$, modulo $998244353$.
Note that identical triangles (those that differ only by swapping $P$ and $Q$) are counted only $1$ time.

Input

$N$

  • $N$ is a positive integer satisfying $1\leqq N\leqq 10^{12}$.

Output

Output on $1$ line the sum of the joy modulo $998244353$.
Print a newline at the end.

Sample

Sample 1
Input
1
Output
8

For example, $P(1,0)$, $Q(0,1)$ gives a minimal lattice triangle. This triangle yields a joy of $2$. The $4$ triangles obtained by rotating this triangle about $O$ in steps of $90$ degrees are the ones to be counted.

Sample 2
Input
25
Output
1208

For example, $P(4,-3)$, $Q(-3,2)$ gives a minimal lattice triangle. This triangle yields a joy of $12$.

Sample 3
Input
1000000
Output
741919871

Output the value modulo $998244353$.

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