1970.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1970 on 2006-01-11 at 17:45:14 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 1024;

bool div(char*, int&, int);

int main()
{
	int nn[10], i, j;
	char digit[MAX];
	
	while(scanf("%s", digit) != EOF && strcmp(digit, "-1")) {
		memset(nn, 0, sizeof(nn));
		int l = strlen(digit);
		if(l == 1) printf("1%s\n", digit);
		else {
			while(digit[l-1] == '0') nn[2]++, nn[5]++, l--;
			int p = (l+1) / 2;
			for(i = 0; i < p; i++) {
				char t = digit[i] - '0';
				digit[i] = digit[l-1-i] - '0';
				digit[l-1-i] = t;
			}
			while(digit[0] % 2 == 0) nn[2]++, div(digit, l, 2);
			while(digit[0] % 5 == 0) nn[2]++, div(digit, l, 2);
			while(true) {
				int s = 0;
				for(i = 0; i < l; i++) s += digit[i];
				if(s % 9 == 0) nn[9]++, div(digit, l, 9);
				else if(s % 3 == 0) nn[3]++, div(digit, l, 3);
				else break;
			}
			while(div(digit, l, 7)) nn[7]++;
			if(l != 1 || digit[0] != 1) printf("There is no such number.\n");
			else {
				nn[8] = nn[2] / 3; nn[2] %= 3;
				nn[9] += nn[3] / 2; nn[3] %= 2;
				if(nn[3] == 1 && nn[2] > 0) nn[3]--, nn[2]--, nn[6]++;
				nn[4] = nn[2] / 2; nn[2] %= 2;
				for(i = 0; i < 10; i++) 
					for(j = 0; j < nn[i]; j++)
						putchar(i+'0');
				putchar('\n');
			}
		}
	}
	
	return 0;
}

bool div(char* d, int& l, int m)
{
	if(l == 1 && d[0] % m != 0) return false;
	else {
		int i, r = 0;
		for(i = l-1; i >= 0; i--) {
			r = r * 10 + d[i];
			d[i] = r / m;
			r %= m;
		}
		while(d[l-1] == 0) l--;
		return (r == 0);
	}
}