覆盖数字【解】--英雄会

首先看看题目：

给定整数区间[a,b]和整数区间[x,y]，你可以使用任意多次a,b之间的整数做加法，可以凑出多少个[x,y]区间内的整数？ 输入 a,b,x,y，其中1<= a < b <= 1000000000, 1 <= x < y <= 1000000000。

输出： 用[a,b]内的整数做任意多次加法，可以得到多少个[x,y]内的整数。

例如a = 8, b = 10, x = 3 , y = 20 我们可以得到 [3..20]之间的整数 8, 9, 10, 16 （ 8 + 8）, 17（8 + 9）, 18（9 + 9）, 19（9 + 10）, 20（10 + 10），因此输出8。

问：2+3=5 1+4=5 这算1个还是2个？ 答：算1次 问你能覆盖多少个不同的数字 [x,y]全覆盖住得话 就是y - x + 1。

对这样的题目，我们首先得进行分析，由于[a, b]内的整数可以做多次加法，每个数字当然也可以重复任意多次；

第一种：如果a = 1;这样的话我们用n个1肯定可以形成x-y的数，所以，这个时候返回y - x + 1;

第二种：如果a == b;这样的话我们只能a来组成x-y之间的数，这样返回y / a - (x - 1) / a;

第三种：这是一般处理的，我们分别将[a, b]组成[1, x - 1],[1, y]这两个区间数的个数，然后将其相减，即可得到[x, y]区间的数的个数；

给出例子：a = 8, b = 10, x = 3 , y = 20 我们可以得到 [3, 20]之间的整数 8, 9, 10, 16 （ 8 + 8）, 17（8 + 9）, 18（9 + 9）, 19（9 + 10）, 20（10 + 10）

这样的话，由a = 8,b = 10;可以组成8 - 10; 16 - 20; 24 - 30; 32 - 40。。。

它们的个数分别是3 ， 5， 7， 9...（等差数列）

所以，如果a = 8,b = 10; x = 3, y = 20;

我们先算它可以先乘几倍，如b = 10可以乘以两次到达20；

count = num / b;  //倍数

sum = count * ((b - a + 1) + ((b - a) * count + 1)) / 2; //Sn=n(a1+an)/2

这样将之前的整的就求出来了（通过等差数列求和，因为数会到1000000000，如果模拟的话时间是不够的）；

这时候sum = 8;

如果之前的y = 25的话，通过前面的计算后只是到达20而已，后面还有几个数据没有添加进去进行判断是否能够被组成（若y = 25;这样24,25都是可以的；若y = 22这样21,22无法被组成）；

if(num >= (count + 1) * a)
      sum += num - (count + 1) * a + 1;

加上num >= (count + 1) * a是将之前的基准往后移一位，即由16 - 20到24 - 20；

这样的话就可以将剩余的数有效的计算了；

如果我们将之前的a = 8; b = 10继续扩增的话，我们发现8 - 10; 16 - 20; 24 - 30; 32 - 40;40 - 50; 48 - 60。。。这时我们发现 32 - 40; 40 - 50; 48 - 60这些相邻的都会出现重合的部分，并且往后还会继续重合下去...

    if((a % (b - a)) == 0 )
        countnum = a / (b - a);  //(n + 1)a - nb <= 0
    countnum = a / (b - a) + 1;

通过(n + 1)a - nb <= 0；这样我们就可以什么时候会发生重合现象；

如a = 8, b = 10这样countnum = 4;到第五倍的时候就会重合了即40 - 50和前面的32 - 40发生重合；

这样，如果y = 43;

count = 4;

这时：

sum = countnum * ((b - a + 1) + ((b - a) * countnum + 1)) / 2; //Sn=n(a1+an)/2
sum += num - countnum * b;

即将前面的算出来，在40后面的肯定都可以被组合出来，所以会有sum += num - countnum * b;

这样就行了...

主要思想就是这样的，如果大家有什么不清楚的欢迎多多讨论；

由于这个代码英雄会上不便贴出，只上关键的了；

int cover(int a, int b, int num)
{
    int count;  //次数
    int sum = 0;  //表示的数
    int countnum = 0;  //几次之后超过
    if((a % (b - a)) == 0 )
        countnum = a / (b - a);  //(n + 1)a - nb <= 0
    countnum = a / (b - a) + 1;
    count = num / b;
    if(count < countnum)  //前面的数未超限
    {
        sum = count * ((b - a + 1) + ((b - a) * count + 1)) / 2; //Sn=n(a1+an)/2
        if(num >= (count + 1) * a)
            sum += num - (count + 1) * a + 1;
        return sum;
    }
    else  //超限，有重叠
    {
        sum = countnum * ((b - a + 1) + ((b - a) * countnum + 1)) / 2; //Sn=n(a1+an)/2
        sum += num - countnum * b;
        return sum;
    }
}

没想到这一题竟然有三星难度，捡漏了...

成功进入top100...欢迎贺电，嘿嘿

欢迎大神指点...o(∩_∩)o