牛客数对题目详解

• 链接在这里数对

 这道题由于有时间限制，用暴力解法是不用能通过的，而且思路不容被观察出来，所以通过率只有不到15%，今天我带大家来详细解析这道提如何解决，希望能帮助到大家。（个人思路）

• 题目描述：

输入两个正整数，第一个正整数n是这个正整数对的范围，第二个数是数对中两个数的余数，只要这个范围中的某个数对第一个数余数大于等于k即可。

示例一如下

可以看出，要想得到全部数对，可以将他们分为两部分，一部分的x是小于y的，保持余数大于等于提供给的k即可。

• 思路：

先分析第一部分找出规律。

观察规律其实可以很容易可以发现，第一部分是递减序列求和，只要用等差数列求和公式即可算出x大于y部分有多少个数对。

输入n等于5，k等于2，等差数列求和公式为末项减首项乘以项数除以2。

这道题比较麻烦的是后边部分数对个数不好求，当然用实例1根本看不出什么，我们可以举一个更加全面的例子。

假设n=10,k=2。列出全部的符合条件的数对，观察规律。如下

观察啊观察，感觉很乱没有规律可言，其实换一种排布方式就可以找到他们的规律。

规律何在？

规律如下

可以先求出可以整除的，例如第一行中除以3余2，除完后得到得数乘以y-k即可，再求余数中的，例如第二行，（10-4）+1除以4，余数为3,3大于k，所以还要加上所得余数-k，这就是余数中包含的部分。

在看代码前大家可以根据思路自己敲一遍，这道题有很多细节，也很考验逻辑能力。

代码实现（有很多细节都注释了）

int main() {
    int a = 0, b = 0;
    unsigned long long count = 0;
    scanf("%d %d", &a, &b);
    for (int i = b + 1; i <= a; i++)
    {
        unsigned long long num = (a - i) / i;
        count += num * (i - b);//可以整除的部分
        if(b>0)//这里有第二个数为0的情况
        {
            if (((a - i) % i + 1) > b)
            count += (a-i) % i - b+1;//余数部分
        }
        else {
        count+=a%i;//如果为零，直接加上余数即可。
        }
    }
    count += (unsigned long long)(a - b + 1) * (a - b) / 2;//由于a和b都是int类型，要强转long long，不然部分用例通不过。
    printf("%lld", count);
    return 0;
}

运行后就可以顺利通过了。

希望大家有所收获。