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

typedef struct _node {
   int data;
   struct _node *next;
} node;

node *genrho ( int M , int x )
{
   node *head, *p, *q;

   x %= M; if (x < 0) x += M;
   head = (node *)malloc(sizeof(node));
   head -> data = x;
   head -> next = NULL;
   p = head;
   printf("%6d: Inserted... continuing...\n", x);

   while (1) {
      x = (x * x + 1) % M;
      printf("%6d: ", x);
      q = head;
      while (q != NULL) {
         if (q -> data == x) break;
         q = q -> next;
      }
      if (q != NULL) {
         printf("Cycle detected... breaking...\n");
         p -> next = q;
         break;
      } else {
         printf("Inserted... continuing...\n");
         p -> next = (node *)malloc(sizeof(node));
         p = p -> next;
         p -> data = x;
         p -> next = NULL;
      }
   }

   return head;
}

int cyclelen ( node *head )
{
   int l;
   node *p, *q;

   p = q = head;
   do {
      p = p -> next;
      q = q -> next -> next;
   } while (p != q);

   l = 0;
   do {
      ++l;
      q = q -> next;
   } while (p != q);

   return l;
}

int main ()
{
   printf("Run 1: M =   100, x =     5, cycle length = %d\n\n", cyclelen(genrho(100,5)));
   printf("Run 2: M =  6543, x =  3456, cycle length = %d\n\n", cyclelen(genrho(6543,3456)));
   printf("Run 3: M = 35791, x = 13579, cycle length = %d\n\n", cyclelen(genrho(35791,13579)));
   exit(0);
}