1023 Have Fun with Numbers (20 分)

Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!

Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.

Input Specification

Each input contains one test case. Each case contains one positive integer with no more than 20 digits.

Output Specification

For each test case, first print in a line “Yes” if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or “No” if not. Then in the next line, print the doubled number.

Sample Input

1234567899

Sample Output

Yes
2469135798

题意

输入一个k位数，双倍后的结果只是重新双倍前的重新排列。此题考查大整数的乘法，若直接用long long存储双倍后的结果会溢出。

代码

#include <iostream>
#include <map>
#include <cstring>
using namespace std;
map<int,int> m1,m2; //利用map根据键值自动排序，存储两次的数字排列组合
int main() {
	int flag=1;
	char n[22]; //原始数字
	int d[22];  //双倍后数字
	scanf("%s",n);
	for(int i=0; i<strlen(n); i++) {
		m1[n[i]-'0'] ++;
	}
	//大整数的乘法
	int carry=0,len=0;	//进位 
	for(int i=strlen(n)-1;i>=0;i--){
		int temp = n[i]-'0';	//先将字符转为数字
		temp =  temp * 2 + carry;
		m2[temp%10] ++;
		d[len++] = temp % 10;	//个位留下 
		carry = temp / 10;		//十位加到较高位上 
	}
	while(carry!=0){            //进位可能不止一位
		d[len++] = carry % 10;	//个位留下
		carry /= 10;
	}
	if(m1.size()==m2.size()) {  //比较两次的map
		for(int i=0; i<m1.size(); i++) {
			if(m1[n[i]-'0'] != m2[n[i]-'0'])
				flag=0;
		}
	} else {
		flag=0;
	}
	if(flag==1)	printf("Yes\n");
	else	printf("No\n");
	for(int i=len-1;i>=0;i--){  //输出两倍后的结果
		cout << d[i];
	}
	return 0;
}