#include<stdio.h>
#include<stdlib.h>

static void ExhaustiveSearch(int target_length)
{
   int best_x, best_y, max_delta;
   int x, y, seed, next_seed, delta, length;

   puts(__func__);
   best_x = best_y = 0;
   max_delta = -1;
   for(x = 2; x < target_length; x++)
   {
      for(y = 0; y < target_length; y++)
      {
         seed = 0;
         delta = 0;
         for(length = 0; length < target_length; length++)
         {
            next_seed = (seed * x + y) % target_length;
            delta += abs(next_seed - seed);
            seed = next_seed;
            if( seed == 0 )
               break;
         }
         if( seed != 0 || length < target_length - 1 )
            continue;
         if( max_delta < delta )
         {
            best_x = x;
            best_y = y;
            max_delta = delta;
         }
      }
   }

   if( max_delta < 0 )
      printf("No suitable parameters found for length %d\n", target_length);
   else
      printf("seed = seed * %d + %d\n", best_x, best_y);
}

static void FastSearch(int target_length)
{
   int x, y, seed, length;

   puts(__func__);
   for(x = 2; x < target_length; x++)
   {
      for(y = 0; y < target_length; y++)
      {
         seed = 0;
         for(length = 0; length < target_length; length++)
         {
            seed = (seed * x + y) % target_length;
            if( seed == 0 )
               break;
         }
         if( seed != 0 || length < target_length - 1 )
            continue;
         printf("seed = seed * %d + %d\n", x, y);
         return;
      }
   }
}

int main(int argc, char **argv)
{
   int target_length;

   if( argc < 2 )
   {
      printf("%s <cycle length>\n", *argv);
      return 1;
   }
   target_length = atoi(argv[1]);
   if( target_length < 2 )
   {
      puts("Minimum supported cycle length is 2.");
      return 1;
   }

   if( target_length < 2048 )
      ExhaustiveSearch(target_length);
   else
      FastSearch(target_length);
   return 0;
}