// C++ (+gmp)で書いた rho 法。 
// 手抜きで簡単な演算のオーバーライドのみをしてある。
// 本体はずいぶんとUBASIC, RUBY, PYTHON などの言語で書くのと似てくるが、
// その分実行時間は犠牲になる。



//#define DEBUG
#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif
#include<stdio.h>
#include<iostream.h>
#include<stdiostream.h>
#include<streambuf.h>
#include<stdlib.h>
#include<strings.h>
#include<gmp.h>
#include<time.h>
#define overload_bin_function(fn0, fn)\
seisuu operator fn0(const seisuu &m,const seisuu &n){ \
seisuu temp; \
fn(temp.value,m.value,n.value); \
return (temp); \
}
#define overload_bin_function_ui(fn0, fn_ui)\
seisuu operator fn0(const seisuu &m,const unsigned long int i){ \
seisuu temp; \
fn_ui(temp.value,m.value,i); \
return (temp); \
}
#define overload_bin_functions(fn0,fn,fn_ui)\
overload_bin_function(fn0,fn)\
overload_bin_function_ui(fn0,fn_ui)
//**********************************************************************
// 
//  definition of seisuu
//
//**********************************************************************

class seisuu {
	public:
	    //constructors
	seisuu();
	seisuu(const seisuu & n);
	 seisuu(const char *value_string);
	 seisuu(const long int i);
	//destoructor
	~seisuu();
	//operotors
	int operator = (const seisuu n);
	int operator = (const mpz_t n);
	int operator = (const long int n);
	void print(int base);
	mpz_t value;
};

//constructors
seisuu::seisuu()
{
	mpz_init(value);
}


seisuu::seisuu(const seisuu & n)
{
	mpz_init(value);
	mpz_set(value, n.value);
}

seisuu::seisuu(const long int i)
{
	mpz_init(value);
	mpz_set_si(value, i);
}
seisuu::seisuu(const char *value_string)
{
	mpz_init(value);
	mpz_set_str(value, value_string, 0);
}

//destructor
seisuu::~seisuu()
{
	mpz_clear(value);
	debug("destructor  called\n");
}

//operators
int seisuu::operator = (const seisuu n) {
	mpz_set(value, n.value);
	return 0;
}

int seisuu::operator = (const long int i) {
	mpz_set_si(value, i);
	return 0;
}


int seisuu::operator = (const mpz_t n) {
	mpz_set(value, n);
	return 0;
}

overload_bin_functions(+, mpz_add, mpz_add_ui)
    overload_bin_functions(-, mpz_sub, mpz_sub_ui)
    overload_bin_functions(*, mpz_mul, mpz_mul_ui)
    overload_bin_functions(/, mpz_fdiv_q, mpz_fdiv_q_ui)
    overload_bin_functions(%, mpz_mod, mpz_fdiv_r_ui)

unsigned long int mod_ui(const seisuu & n, const unsigned int i)
{
	mpz_t temp;
	unsigned long int l;
	mpz_init(temp);
	l = mpz_fdiv_r_ui(temp, n.value, i);
	mpz_clear(temp);
	return (l);
}

int operator < (const seisuu & m, const seisuu & n) {
	int i;
	int errorlevel = 0;
	i = mpz_cmp(m.value, n.value);
	if (i < 0) {
		errorlevel = 1;
	}
	return (errorlevel);
}
int operator > (const seisuu & m, const seisuu & n) {
	int i;
	int errorlevel = 0;
	i = mpz_cmp(m.value, n.value);
	if (i > 0) {
		errorlevel = 1;
	}
	return (errorlevel);
}

int operator != (const seisuu & m, const seisuu & n) {
	int i;
	int errorlevel = 1;
	i = mpz_cmp(m.value, n.value);
	if (i == 0) {
		errorlevel = 0;
	}
	return (errorlevel);
}

int operator == (const seisuu & m, const seisuu & n) {
	int i;
	int errorlevel = 0;
	i = mpz_cmp(m.value, n.value);
	if (i == 0) {
		errorlevel = 1;
	}
	return (errorlevel);
}



void seisuu::print(int base)
{
	unsigned long long int keta;
	char *t;

	keta = mpz_sizeinbase(value, base);
	t = (char *) malloc(keta + 2);
	mpz_get_str(t, base, value);
	printf("%s", t);

	free(t);
	return;
}

seisuu gcd(seisuu a, seisuu b)
{
	seisuu m;
	mpz_gcd(m.value, a.value, b.value);
	return (m);
}

//***********************************************************************
//
// ここから本体
//
//***********************************************************************
void advance(seisuu &x, seisuu n)
{
	x = (x * x + 1) % n;
	return;
}



int main(void)
{
	seisuu x;
	seisuu n = "607143768775207";
	seisuu a = 2;
	seisuu b = a;
	while (1) {
		advance(a, n);
		advance(b, n);
		advance(b, n);
		x = (a - b) % n;
		if (gcd(x, n) != 1) {
			gcd(x, n).print(10);
			printf("\n");
			break;
		}
	}
	return (0);
}