整数对(数学题)

整数对

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

Gardon和小希玩了一个游戏，Gardon随便想了一个数A（首位不能为0），把它去掉一个数字以后得到另外一个数B，他把A和B的和N告诉了小希，让小希猜想他原来想的数字。不过为了公平起见，如果小希回答的数虽然不是A，但同样能达到那个条件（去掉其中的一个数字得到B，A和B之和是N），一样算小希胜利。而且小希如果能答出多个符合条件的数字，就可以得到额外的糖果。
所以现在小希希望你编写一个程序，来帮助她找到尽可能多的解。
例如，Gardon想的是A=31,B=3 告诉小希N=34，
小希除了回答31以外还可以回答27（27+7=34）所以小希可以因此而得到一个额外的糖果。

Input

输入包含多组数据，每组数据一行，包含一个数N(1<=N<=10^9)，文件以0结尾。

Output

对于每个输入的N，输出所有符合要求的解（按照大小顺序排列）如果没有这样的解，输出"No solution."

Sample Input

Sample Output

27 31 32
126 136 139 141
No solution.


//有点难的数学题
先从个例开始分许，如果你想的数是 12345 ，将第三位的数去掉， 1245 ，与 12345 相加得到 13590
所以，可以把 12345 看成这样的结构 12 * 10^3 + 3 * 10^2 + 45 ， 1245 就是 12 * 10^2 + 45
13590 就是 12  * 10^3 + ( 3 + 12 ) * 10^2 + 45 * 2
推广一下，就是去掉一个数的 k 位的话 ，就是 a * 10^k + b * 10^(k-1) + c  去加 a * 10^(k-1) + c  
和为 ( 11a + b ) * 10^(k-1) + 2c
所以每个数都有这种结构，将 N 这个数 /1 /10 /100 ..../i  除到 <= N 相当于去掉 2*C
a = (N/i)/11
b = (N/i)%11
2c 可能会进位，所以 b 要分情况讨论，不进位很简单。
进位的话还要 a 和 b 不能都为 0 不然，例如 1000 会多输出个500，想下为什么

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int ans[1000];
 6 
 7 int main()
 8 {
 9     int N;
10     int a,b;
11     while (cin>>N&&N)
12     {
13         int res=0;
14         for (int i=1;i<=N;i*=10)//这样就相当于去掉 C
15         {
16             a=(N/i)/11;
17             b=(N/i)%11;
18             int c;
19             if (b<10)//可能没进位的情况
20             {
21                 c =(N - N/i*i)/2;
22                 if ( ( (11*a+b)*i+2*c )==N)
23                 ans[res++]=a*i*10+b*i+c;
24             }
25             b--;//进位的情况
26             if (a+b&&b>=0)
27             {
28                 c =(N - N/i*i+ i)/2;
29                 if (((11*a+b)*i+2*c )==N)
30                 ans[res++]=a*i*10+b*i+c;
31             }
32         }
33         if (res)
34         {
35             sort(ans,ans+res);
36             cout<<ans[0];
37             for (int i=1;i<res;i++)
38                 if(ans[i]!=ans[i-1])
39                     cout<<' '<<ans[i];
40             cout<<endl;
41         }
42         else
43             printf("No solution.
");
44     }
45     return 0;
46 }

View Code