题目

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:

1

1234567899

Sample Output:

1
2

Yes
2469135798

思路

主要是大数运算，这里是大数和个位数的乘法，我的简要思路是：

  • 用字符数组倒序存储数字，即小序数的地方存低位数字。
  • 做乘法，模拟手算，注意字符和数字的转换：
    • s代表算出的当前位，
    • l代表当前剩余的进位数字，在下一次计算时，加上此数字。
  • 将结果再翻转回来，便于输出。
  • 统计两个数包含数字的数量之差，按要求输出即可。

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <stdio.h>
#include <string.h>

void reverse(char n[])
{
	char temp;
	int len = strlen(n);
	for (int i = 0; i < len / 2; i++) {
		temp = n[i];
		n[i] = n[len - i - 1];
		n[len - i - 1] = temp;
	}
}

void doubleLargeNumber(char n[], char n2[])
{
	int l, s = 0, len = strlen(n);

	for (int i = 0; i < len; i++) {
		s += 2 * (n[i] - '0');
		l = s / 10;
		s %= 10;
		n2[i] = s + '0';

		s = l;
	}

	if (s)
		n2[len] = s + '0';
}

int main()
{
	char N[22] = {0}, N2[22] = {0};
	int diffcount[10] = {0};

	scanf("%s", N);
	/* store number in reverse order */
	reverse(N);
	doubleLargeNumber(N, N2);
	/* reverse back (just need N2) for printing */
	reverse(N2);

	/* Count the difference of counts of digits 0-9 */
	for (int i = 0; i < strlen(N); i++)
		diffcount[N[i] - '0']++;
	for (int i = 0; i < strlen(N2); i++)
		diffcount[N2[i] - '0']--;

	/* Check */
	for (int i = 0; i < 10; i++)
		if (diffcount[i]) {
			printf("No\n%s", N2);
			return 0;
		}
	printf("Yes\n%s", N2);

	return 0;
}