Triples

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ⁿ + yⁿ = zⁿ 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³ 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 }