1381.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
int xr,xi,br,bi;
int a[110],n;

bool doit()
{
	int i,value=br*br+bi*bi,xrt,xit;
	if(xr==xi&&xi==0)
	{
		a[0]=0;
		n=1;
		return 1;
	}

	for(i=0;i<=100&&(xr||xi);i++)
	{
		for(a[i]=0;a[i]*a[i]<value;a[i]++)
		{
			if( ((xr-a[i])*br+xi*bi)%value==0  &&  (xi*br-(xr-a[i])*bi)%value==0 )
				break;
		}
		if(a[i]*a[i]>=value)return 0;
		
		xrt=((xr-a[i])*br+xi*bi)/value;
		xit=(xi*br-(xr-a[i])*bi)/value;

		xr=xrt,xi=xit;
	}
	n=i;
	return xr==0&&xi==0;
}

int main()
{
	int t,i;
	cin>>t;
	while(t--)
	{
		cin>>xr>>xi>>br>>bi;
		if(!doit())
			cout<<"The code cannot be decrypted."<<endl;
		else
		{
			for(i=n-1;i>=0;i--)
			{
				cout<<a[i];
				if(i)cout<<',';
			}
			cout<<endl;
		}
	}
	return 0;
}