Let **m** and **n** be two positive integers, **5 ≤ m ≤ 100, 2 ≤ n ≤ 100**. Consider the following sets of triples:

**T**

_{m,j}= {(x, y, z) ∈ ℕ^{3}| x ≤ y ≤ z ≤ m and x^{j}+ y^{j}= z^{j}}, j = 2…nThe problem asks you to compute the sum:

**S**.

_{m,n}= ∑ card(T_{m,j}), 2 ≤ j ≤ n*Notes*:

- ℕ is the set of non-negative integers (ℕ =
**{0, 1, 2, …}**). **card(T**is the number of elements of the set_{m,j})**T**._{m,j}

## Input

The input contains several test cases. Each test case occupies exactly two lines of input: the first line contains integer **m**, and the second line contains integer **n**. Tests should be read until the end of file is reached.

## Output

For each test case, the result will be written to standard output, on a line by itself.

## Sample

Input | Output |
---|---|

8595 | 8128 |

Solution by Gabriel Inelus.

In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture) states that no three positive integers x, y, and z can satisfy the equation `x ^{n} + y^{n} = z^{n}` for any integer value of n greater than two. However, during the contest it was easy to observe this by using a brute force algorithm which tests all tuples

`{(x,y,z,j) | x^j + y^j = z^j , 0 <= x <= y <= z <= M}`.

Hence, we can use a M^{3} algorithm to count all `(x,y,z,2)` tuples and than for each `j ≥ 3`, we have only tuples like `(0,x,x,j)`>. There are `N-2` powers of `j >= 3` and there are `M+1` possible values of x for each power of j. Thus, we add `(N-2)*(M+1)` to the solution. The algorithm is repeated for each input set and the final complexity is `M^3*T`.

1 #include<stdio.h> 2 3 int main() { 4 int n, m, i, j, k; 5 while(scanf("%d%d", &m, &n) == 2) { // Read all imput sets 6 int total = 0; 7 8 for(i = 0; i <= m; ++i) 9 for(j = i; j <= m; ++j) 10 for(k = j; k <= m; ++k) 11 if(i*i + j*j == k*k) // Test for x^2 + y^2 = z^2 12 total++; 13 14 total += (m + 1) * (n - 2); // Add the remaining tuples 15 printf("%d\n",total); 16 } 17 return 0; 18 }