1 /* This solution precomputes all answers.
    2  *
    3  * Author: Matt Eastman
    4  */
    5 
    6 #include <assert.h>
    7 #include <stdint.h>
    8 #include <stdio.h>
    9 #include <stdlib.h>
   10 
   11 #define MAX_SQUARES 1000000
   12 #define MAX_ANSWERS 1005    // at least sqrt(MAX_SQUARES)
   13 
   14 int answers[MAX_ANSWERS];
   15 
   16 void BuildAnswers()
   17 {
   18   uint16_t* num_factors = (uint16_t*)calloc(MAX_SQUARES + 1, sizeof(uint16_t));
   19   assert(num_factors != NULL);
   20   int factor, i;
   21   for (factor = 1; factor * factor <= MAX_SQUARES; factor++)
   22     {
   23       for (i = factor * factor; i <= MAX_SQUARES; i += factor)
   24         {
   25           num_factors[i]++;
   26         }
   27     }
   28   for (i = 1; i <= MAX_SQUARES; i++)
   29     {
   30       if (answers[num_factors[i]] == 0)
   31         answers[num_factors[i]] = i;
   32     }
   33   free(num_factors);
   34 }
   35 
   36 int main(int argc, char** argv)
   37 {
   38   BuildAnswers();
   39 
   40   int num_inputs, i, num;
   41   assert(scanf(" %d", &num_inputs) == 1);
   42 
   43   for (i = 0; i < num_inputs; i++)
   44     {
   45       assert(scanf(" %d", &num) == 1);
   46       if (num < MAX_ANSWERS && answers[num])
   47         printf("%d\n", answers[num]);
   48       else
   49         printf("Too big\n");
   50     }
   51 
   52   return 0;
   53 }
   54