zoj3327——Friend Number

题意&思路 参见http://apps.hi.baidu.com/share/detail/16155270

数学题！在比赛中做出的非牛即牛啊！！！

#include<iostream>
#include<cstring>
using namespace std;
char num[1005];
char tt[1005];
int net[5],kk[1005],len;
void ok(int end)
{
	int i,j,k;
	for(i=0;i<=end;i++)
		cout<<num[i];
	j=0;
	for(i=end+1;i<len;i++)
	{
		if(net[1]>=2){net[1]-=2;kk[j++]=9;}
	    else if(net[0]>=3){net[0]-=3;kk[j++]=8;}
		else if(net[3]>=1){net[3]--;kk[j++]=7;}
		else if(net[0]>=1&&net[1]>=1){net[1]--;net[0]--;kk[j++]=6;}
		else if(net[2]>=1){net[2]--;kk[j++]=5;}
		else if(net[0]>=2){net[0]-=2;kk[j++]=4;}
		else if(net[1]>=1){net[1]--;kk[j++]=3;}
		else if(net[0]>=1){net[0]--;kk[j++]=2;}	
		else {kk[j++]=1;}
	}
	for(i=j-1;i>=0;i--)
		cout<<kk[i];
	cout<<endl;
}
void solve()
{
	int i,j,k;
	bool flag1=false,flag2=false;
	len=strlen(num);
	if(num[len-1]=='0') flag1=true;
	for(i=0;i<len-1;i++)
		if(num[i]=='0')
			flag2=true;
	if(flag2)
	{
		k=num[len-1]-'0'+1; bool jin=false;
		if(k>9) {k=0;jin=true;}
		i=1;tt[0]=k+'0';
		for(j=len-2;j>=0;j--)
		{
			k=num[j]-'0';
			if(jin) k++;
			if(k>9) {k=0;jin=true;}
			else jin=false;
			tt[i]=k+'0';
			i++;
		}
		for(j=i-1;j>=0;j--) cout<<tt[j];
		cout<<endl;
		return ;
	}
 	if(flag1&&!flag2) //只有一个末尾0
	{
		tt[0]='0';bool jin=false;
		k=num[len-2]-'0'+1;
		if(k>9) {k=0;jin=true;}
		tt[1]=k+'0';i=2;
		for(j=len-3;j>=0;j--)
		{
			if(jin)
				k=num[j]-'0'+1;
			else k=num[j]-'0';
			if(k>9) {k=0;jin=true;}
			else jin=false;
			tt[i]=k+'0';
			i++;
		}
		if(jin)
		{ tt[i++]=1+'0';}
		for(j=i-1;j>=0;j--)cout<<tt[j];
		cout<<endl;
		return ;
	}
	if(len>=2)
	{
		int a=num[len-2]-'0';int b=num[len-1]-'0';
  		if(a<b)
		{
			for(i=11;i<=99;i++)
				if((a*b==(i%10*(i/10)))&&(i>(a*10+b)))
				{
					a=i/10;b=i%10;
					break;
				}
   			num[len-2]=a+'0';num[len-1]=b+'0';
			for(i=0;i<len;i++) cout<<num[i];
			cout<<endl;
			return ;
		}
	}
	if(len==1)
	{
		int a=num[0]-'0';
		for(i=11;i<=20;i++)
			if(a==(i%10*(i/10)))
			{
				cout<<i<<endl;
				return ;
			}
	}
	memset(net,0,sizeof(net));
	bool flag=false;
	for(i=len-1;i>=0;i--)
	{
		 int a=num[i]-'0',b;b=a;
		 while(b!=1)
		 {
   			 if(b%2==0) {net[0]++;b/=2;}
			 else if(b%3==0) {net[1]++;b/=3;}
			 else if(b%5==0) {net[2]++;b/=5;}
			 else if(b%7==0){net[3]++;b/=7;}
		 }
		 if(flag){}
		 else 
		 {
			 if(net[0]>=1&&2>a){net[0]--;num[i]=2+'0';ok(i);flag=true;}
			 else if(net[1]>=1&&3>a){net[1]--;num[i]=3+'0';ok(i);flag=true;}
			 else if(net[0]>=2&&4>a){net[0]-=2;num[i]=4+'0';ok(i);flag=true;}
			 else if(net[2]>=1&&5>a){net[2]--;num[i]=5+'0';ok(i);flag=true;}
			 else if(net[0]>=1&&net[1]>=1&&6>a){net[1]--;net[0]--;num[i]=6+'0';ok(i);flag=true;}
			 else if(net[3]>=1&&7>a){net[3]--;num[i]=7+'0';ok(i);flag=true;}
			 else if(net[0]>=3&&8>a){net[0]-=3;num[i]=8+'0';ok(i);flag=true;}
			 else if(net[1]>=2&&9>a){net[1]-=2;num[i]=9+'0';ok(i);flag=true;}
		 }
		 if(flag) break;
	}
	if(flag==false)
	{cout<<1;ok(-1);}
}
int main()
{
	int ca;
	cin>>ca;
	cin.getline (num,1005);
	for(int i=0;i<ca;i++)
	{
		cin.getline (num,1005);
		solve();
	}
	return 0;
}