201251: [AtCoder]ARC125 B - Squares

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

Problem Statement

You are given an integer $N$. Find the number of pairs of integers $(x, y)$ that satisfy the following conditions, modulo $998244353$.

  • $1 \leq x,y \leq N$.

  • $x^2-y$ is a square number. (Assume $0$ is also a square number.)

Constraints

  • $1 \leq N \leq 10^{12}$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the answer.


Sample Input 1

3

Sample Output 1

2

We have the following two pairs.

  • $x=1,y=1$

  • $x=2,y=3$


Sample Input 2

10

Sample Output 2

8

Sample Input 3

10000000000

Sample Output 3

52583544

Input

题意翻译

现在给你一个数 $N$,求出满足下列条件的点对 $(x,y)$ 的个数对 998244353 取模后的值。 - $1\le x,y \le N$ - $x^2-y$ 是一个完全平方数。特别的,0 也算一个完全平方数。 输入一个数,表示 $N$。 输出一个数,表示满足条件的点对的个数对 998244353 取模后的值。

加入题单

上一题 下一题 算法标签: