Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不过确实有他的国人之处,也就算拉。第这个算法比较欣赏!

Posted by feng2017 at 2006-08-12 11:16:37 on Problem 1006
In Reply To:0MS 的程序,运用辗转相除法联立方程直接求解,最多一层循环 Posted by:2_080310236 at 2006-03-04 21:58:46
> #include "iostream.h" 
> #include "math.h"
> 
> void Get_Special_Solution(int a,int b,int N,int x[2])
> {
> 	int x1[2]={0},x2[2]={0},temp,flag1=1,flag2=1;
> 	if(N<0) {a=-a;b=-b;N=-N;}
> 	if(N==0) {x[0]=-b,x[1]=a;return;}
> 	if(abs(a)<abs(b))	{temp=a;a=b;b=temp;}
> 	if(a>0 && b<0)		{b=-b;flag2=-1;}
> 	else if(a<0 && b>0) {a=-a;flag1=-1;}
> 	else if(a<0 && b<0) {a=-a;b=-b;}
> 	int m=a,n=b,q1,q2,r1,r2,temp1,temp2;
> 	q1=a/b,r1=a%b;q2=n/r1;r2=b%r1;
> 	m=r1;n=r2;	
> 	x1[0]=1,     x1[1]=-q1;      //r1=a-q1*b;
> 	x2[0]=-q2,   x2[1]=q1*q2+1;  //r2=b-q2*r1;两个递推式来实现辗转相除法的求解过程
> 	if(!r2)	{x[0]=flag1*x1[0];x[1]=flag2*x1[1];return;}
>     while(r2!=1)
> 	{
> 		temp1=x1[0];temp2=x1[1];
> 		x1[0]=x2[0];x1[1]=x2[1];
> 		q2=m/n;r2=m%n;
> 		x2[0]=-q2*x2[0]+temp1;
> 		x2[1]=-q2*x2[1]+temp2;
> 		m=n;n=r2;
> 	}
> 	x[0]=flag1*x2[0];x[1]=flag2*x2[1];
> 	x[0]*=N;x[1]*=N;
> }
> 
> void Show_Equation_Solve(int a[])
> {
> 	int x[2],y[2],z[2],k1,k2;
> 	Get_Special_Solution(28,-23,a[0]-a[1],x);
> 	while(x[0]>0 && x[1]>0)  {x[0]-=23;x[1]-=28;}
> 	while(x[0]<=0||x[1]<=0)    {x[0]+=23;x[1]+=28;} 
> 	Get_Special_Solution(33,-28,a[1]-a[2],y);
> 	while(y[0]>0 && y[1]>0)  {y[0]-=28;y[1]-=33;}
> 	while(y[0]<=0||y[1]<=0)    {y[0]+=28;y[1]+=33;} 
> 	if(x[0]!=y[1])           Get_Special_Solution(33,-23,x[0]-y[1],z);
> 	while(z[0]>0 && z[1]>0)  {z[0]-=23;z[1]-=33;}
> 	while(z[0]<=0||z[1]<=0)    {z[0]+=23;z[1]+=33;} 
> 	a[0]=28*z[1]+x[1],a[1]=23*z[1]+x[0],a[2]=28*z[0]+y[0];
> }
> 
> void main()
> {
> 	int i=0,m,days;
>    	int a[4];
> 	while(1)
> 	{
> 		cin>>a[0]>>a[1]>>a[2]>>a[3];
> 		if(a[0]==a[1] && a[1]==a[2] && a[2]==a[3] && a[3]==-1) break;
> 		m=a[0];
> 		Show_Equation_Solve(a);
> 		cout<<"Case "<<++i<<": the next triple peak occurs in "<<(a[0]*23+21252+m-a[3]-1)%21252+1<<" days."<<endl;
> 	}
> }
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator