Repeat Number（数论）

Repeat Number

题目描述：

Definition: a+b = c, if all the digits of c are same ( c is more than ten)，

then we call a and b are Repeat Number.

My question is How many Repeat Numbers in [x,y].

输入

There are several test cases.

Each test cases contains two integers x, y(1<=x<=y<=1,000,000) described above.

Proceed to the end of file.

输出

For each test output the number of couple of Repeat Number in one line.

样例输入

1 10

10 12

样例输出

提示：

If a equals b, we can call a, b are Repeat Numbers too, and a is the Repeat Numbers for itself.

题目大意：

　　　　　输入一个范围[x,y]，判断在这个范围内能够找到多少组<a,b>使得a+b=c，

　　　　　c需要满足每一位上的数全都一样并且 c > 10。

解题思路：

　　　　先根据题目中给定的范围，将范围内所有满足条件的c存入数组。

　　　　然后根据输入的范围求出最小范围x+x和最大范围y+y，在该范围

　　　　内找满足条件的组合。

AC代码：

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <math.h>

 #include <stdlib.h>

 using namespace std;

 int aa[];

 int f()   // 将满足情况的c值存入数组

 {

     int i,j,k=;

     for (i = ; i < ; i=i*+)

         for (j = ; j <= ; j ++)

             aa[k ++] = i*j;

     aa[k] = ;   // 不要忘记这个最大的哦（1111111  在这个最大的范围内 1000000+1000000）

 }

 int main ()

 {

     f();

     int a,b,j,i;

     while (scanf("%d%d",&a,&b)!=EOF)

     {

         int sum = ;

         for (i = ; i < ; i ++)

         {

             if (a* <= aa[i] && aa[i] <= b*)  // 判断是否在[a+a,b+b]范围内

                 sum += min(aa[i]/-a+,b-(aa[i]+)/+);

         }

         printf("%d\n",sum);

     }

     return ;

 }

 /*

  sum += min(aa[i]/2-a+1,b-(aa[i]+1)/2+1);

  关于以上代码的解释：

  举一个简单的例子  假如输入的x，y为1 10

  只有一个11在[2,20]范围内

  想一想那些数能够组合成11

  （1，10）（2,9）（3,8）（4,7）（5,6）这五个

  以（5,6）这一组为分界

  （1（2（3（4（5,6）7）8）9）10）

  假如输入的x，y为3 10

  也只有一个11在[6,20]范围内

  满足条件的组合

  （3,8）（4,7）（5,6）这五个

  以（5,6）这一组为分界

 （3（4（5,6）7）8）

 所以，根据c/2 到x和y的距离就能判断出有多少组合（选择较小值）

  */

巴特西

Repeat Number（数论）

最新文章

热门文章