QuadraticIdentity | Topcoder Archive

Problem Statement

Bob likes playing with numbers. Recently he found out that (25² mod 100) = (625 mod 100) = 25, and that 16² mod 20 = 16. Mathematically speaking, 25 is a fixed point of squaring modulo 100 and 16 is a fixed point of squaring modulo 20. Bob now wonders whether he just got incredibly lucky, or whether there are many numbers like that.

For a given modulus m, find all fixed points of the function f(x) = x² mod m.

Let A be an array that contains all the distinct values x such that 0 <= x < m and x = (x² mod m), sorted in increasing order. Compute the array A. If A has at most 500 elements, return it.

Otherwise, to keep the output reasonably small, we will compress A as follows: While A has strictly more than 500 elements, repeatedly discard all elements whose indices are odd. (Each iteration of this cycle reduces A to approximately half of its previous length.) Once A has 500 or fewer elements, return it. For example, if the actual array A has 1011 elements, you would return an array with 253 elements. These would be the elements that had indices 0, 4, 8, 12, ... in the original array A.

Definition

Class:: QuadraticIdentity
Method:: getFixedPoints
Parameters:: long
Returns:: long[]
Method signature:: long[] getFixedPoints(long m)
(be sure your method is public)

Notes

It can be shown that under the constraints of the problem there are never more than 105 fixed points.

Constraints

m will be between 1 and 1015, inclusive.

Examples

```
20
```
```
Returns: {0, 1, 5, 16 }
```
The values 0 and 1 are fixed points for squaring modulo any m >= 2. We can easily verify that (52 mod 20) = (25 mod 20) = 5, hence 5 is also a fixed point of squaring modulo 20. The fourth one is mentioned in the problem statement. We can also verify that no other numbers between 0 and 19, inclusive, have this property. For example, (72 mod 20) = (49 mod 20) = 9, and 7 is not 9, hence 7 is not a fixed point in this case.

4262046602

Returns: {0, 1, 27391046, 152613648, 180004693, 333799345, 361190390, 513804038, 541195083, 621181264, 648572309, 801185957, 828577002, 941255910, 968646955, 982371654, 1009762699, 1121260603, 1148651648, 1162376347, 1189767392, 1302446300, 1329837345, 1482450993, 1509842038, 1589828219, 1617219264, 1769832912, 1797223957, 1951018609, 1978409654, 2103632256, 2131023301, 2131023302, 2158414347, 2283636949, 2311027994, 2464822646, 2492213691, 2644827339, 2672218384, 2752204565, 2779595610, 2932209258, 2959600303, 3072279211, 3099670256, 3113394955, 3140786000, 3252283904, 3279674949, 3293399648, 3320790693, 3433469601, 3460860646, 3613474294, 3640865339, 3720851520, 3748242565, 3900856213, 3928247258, 4082041910, 4109432955, 4234655557 }

```
7
```
```
Returns: {0, 1 }
```

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.