euclid.cpp

欧几里德算法和一些其他的简单功能。 求最大公约数之类

#include <iostream.h>
#include <stdlib.h>
#include <math.h>

long int Gcd(long int a,long int b)
{
	long int r;
	if(a<b)
	{
		r=a;
		a=b;
		b=r;
	}
	while(b!=0)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}

// b mod m
long int MulInverse(long int m,long int b)
{
	long int a1,a2,a3,b1,b2,b3,t1,t2,t3;
	int q=0;
	a1=1;
	a2=0;
	a3=m;
	b1=0;
	b2=1;
	b3=b;

	while(b3!=0)
	{
		cout<<q<<"**"<<a1<<"**"<<a2<<"**"<<a3<<"**"<<b1<<"**"<<b2<<"**"<<b3<<endl;
		if(b3==1)
			return b2;
		q=a3/b3;
		t1=a1-q*b1;
		t2=a2-q*b2;
		t3=a3-q*b3;
		a1=b1;
		a2=b2;
		a3=b3;
		b1=t1;
		b2=t2;
		b3=t3;
	}
	cout<<q<<"**"<<a1<<"**"<<a2<<"**"<<a3<<"**"<<b1<<"**"<<b2<<"**"<<b3<<endl;
	cout<<b<<" no inverse"<<endl;
	return Gcd(m,b);

}

int cycle(int a)
{
	int i,j,x,x1,y;
	j=1;
	for(x=1;x<16;x++)
	{
		i=1;
		x1=1;
		y=x;
		y=(a*y)%16;
		while(y!=x)
		{
			i++;
			y=(a*y)%16;
			if(!y)return 0;
		}
		if(j<i)j=i;
	}
	return j;
}

double pi(double x)
{
	return sqrt(1-x*x);
}

double example1(double x)
{
	return x;
}

/*double hitormiss(double (*p)(double t),double n)
{
	int i,k=0;
	double x,y;
	for(i=0;i<n;i++)
	{
		x=rand()/32767.0;
		y=rand()/32767.0;
		//if(y<=(*p)(x))++k;
		if(y<=sqrt(1-x*x))++k;
	}
	return 4*k/n;
}*/

double hitormiss(double a,double b,double c,double d,double (*p)(double t),double n)
{
	int i,k=0;
	double x,y;
	for(i=0;i<n;i++)
	{
		x=a+(b-a)*rand()/32767.0;
		y=c+(d-c)*rand()/32767.0;
		if(y<=(*p)(x))++k;
		//if(y<=sqrt(1-x*x))++k;
	}
	return c*(b-a)+(d-c)*(b-a)*k/n;
}



void main()
{
	int i;
	//cout<<MulInverse(37,22)<<endl;
	//cout<<(56*56*4+4*22*22)%77;
	/*i=(((long int)pow(9,3))%55);
	cout<<i<<endl;
	i=(((long int)pow(i,27))%55);*/
	for(i=1;i<60
	cout<<i<<endl;
}