EquationSolver | Topcoder Archive

Problem Statement

You are given the long n and the int c.

We are interested in n-tuples (x₁, ..., x_n) with the following properties:

Each x_i is a nonnegative integer.
x₁² + x₂² + ... + x_n² = c.

Compute and return the number of such tuples, modulo 998,244,353.

Definition

Class:: EquationSolver
Method:: findNumberOfSolution
Parameters:: long, int
Returns:: int
Method signature:: int findNumberOfSolution(long n, int c)
(be sure your method is public)

Constraints

n will be between 1 and 10^18, inclusive.
c will be between 1 and 10^6, inclusive.

Examples

```
3
```
```
1
```
```
Returns: 3
```
The three tuples are (0,0,1), (0,1,0), and (1,0,0).
```
1
```
```
49
```
```
Returns: 1
```
The only such tuple is (7).
```
1
```
```
47
```
```
Returns: 0
```
As 47 is not a square, there are no solutions.
```
100
```
```
4321
```
```
Returns: 45606298
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.