HDU 1271 整数对

这个题算是数论类吧，也许也就是水题级别，不过我估计是很难想出来的````

首先你自己拿个数试一下比较好看出来规律。

比如 A = 3457

拿掉数字5

B = 347

把A写成34*10^2+5*10^1+7

B写成34*10+7

更一般地，如果拿掉的是第k位数字（0<=k<=log10(N)）,A = a*10^(k+1)+b*10^k+c.(其中a为数字b之前的数，c为数字b之后的数)

然后B = a*10^k+c

有方程A+B=N，带入，得11*10^k*a+10^k*b+2*c = N,

10^k*b<=9*10^k,2*c<2*10^k ，所以有10^k*b+2*c < 11*10^k，那么a = N/（11*10^k）- (10^k*b+2*c)/(11*10^k）,在用整数做除法时，后一项=0。

这样a = N/（11*10^k）

然后枚举b从0到9，再算d = N-(11*a+b)*k;

如果d>=0&&d%2==0&&d<10^k，那么就得到一个可行解A=a*10^(k+1)+b*10^k+d/2.

贴代码：

View Code

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int main()
 5 {
 6 //    freopen("in.cpp","r",stdin);
 7     int n;
 8     int p[110];
 9     while(scanf("%d",&n),n!=0)
10     {
11         int a,b,c,k;
12         int cur = -1;
13         for(k=1; k<= n; k *= 10)
14         {
15             a = n/(11*k);
16             for(b=0; b<=9; ++b)
17             {
18                 if(a == 0 && b==0) continue;
19                 c = n-(11*a+b)*k;
20                 if(c >= 0 && c%2 == 0 && c/2 < k)
21                 {
22                     c = c/2;
23                     p[++cur] =(10*a+b)*k+c;
24                 }
25             }
26         }
27         if(cur == -1)
28         {
29             printf("No solution.\n");
30             continue;
31         }
32         sort(p,p+cur+1);
33         printf("%d",p[0]);
34         for(int i=1; i<=cur; ++i)
35         {
36             if(p[i] != p[i-1])
37             {
38                 printf(" %d",p[i]);
39             }
40         }
41         puts("");
42     }
43     return 0;
44 }