1056B.md (1847B)
1 Source: https://codeforces.com/problemset/problem/1056/B 2 3 B. Divide Candies 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Arkady and his friends love playing checkers on an $n \times n$ field. The rows and the columns of the field are enumerated from $1$ to $n$. 22 23 The friends have recently won a championship, so Arkady wants to please them with some candies. Remembering an old parable (but not its moral), Arkady wants to give to his friends one set of candies per each cell of the field: the set of candies for cell $(i, j)$ will have exactly $(i^2 + j^2)$ candies of unique type. 24 25 There are $m$ friends who deserve the present. How many of these $n \times n$ sets of candies can be split equally into $m$ parts without cutting a candy into pieces? Note that each set has to be split independently since the types of candies in different sets are different. 26 27 Input 28 29 The only line contains two integers $n$ and $m$ ($1 \le n \le 10^9$, $1 \le m \le 1000$) — the size of the field and the number of parts to split the sets into. 30 31 Output 32 33 Print a single integer — the number of sets that can be split equally. 34 35 Examples 36 37 Input 38 39 ``` 40 3 3 41 ``` 42 43 Output 44 45 ``` 46 1 47 ``` 48 49 Input 50 51 ``` 52 6 5 53 ``` 54 55 Output 56 57 ``` 58 13 59 ``` 60 61 Input 62 63 ``` 64 1000000000 1 65 ``` 66 67 Output 68 69 ``` 70 1000000000000000000 71 ``` 72 73 Note 74 75 In the first example, only the set for cell $(3, 3)$ can be split equally ($3^2 + 3^2 = 18$, which is divisible by $m=3$). 76 77 In the second example, the sets for the following cells can be divided equally: 78 79 * $(1, 2)$ and $(2, 1)$, since $1^2 + 2^2 = 5$, which is divisible by $5$; 80 * $(1, 3)$ and $(3, 1)$; 81 * $(2, 4)$ and $(4, 2)$; 82 * $(2, 6)$ and $(6, 2)$; 83 * $(3, 4)$ and $(4, 3)$; 84 * $(3, 6)$ and $(6, 3)$; 85 * $(5, 5)$. 86 87 In the third example, sets in all cells can be divided equally, since $m = 1$.