刷题记录：牛客-WY49数对 | 以数学分析来破解暴力搜索的时间复杂度问题 2023/1/11

一、题干

WY49 数对https://www.nowcoder.com/practice/bac5a2372e204b2ab04cc437db76dc4f

二、题解

暴力搜索的思路是非常容易想到的，将 x 和 y 分别遍历 [1, n] ，进行判断当 x % y > k 时统计计数 count++ 即可。但事实上这样的代码在牛客在线OJ中是跑不过的，因为它的时间复杂度高大O(N)，当问题规模非常大时，循环次数将非常恐怖。

意识到暴力搜索不可行后，我本猜测该题会有巧妙的大招tips来求解，比如运用某种模型来破解暴力搜索。但在看了题解之后我发现，并没有什么现成的“大招”，而是纯粹以数学思维来推导解题公式。

这我还是蛮有收获的，因为就我本人而言，在编写代码时，往往重点在思考有没有模型可用，而耐不下心来慢慢数学分析，或不知道从何入手。这一道题又正是一道数学类型的题，因此，数学分析的思维和方式需要我或与我有同样问题的大家共同熟悉、学习。

以下两种方式是在题解中看到的。但题解中的解释比较简略，我在尝试看懂之后，对该代码进行剖析。

1.方法一：枚举 -- 寻找余数个数规律，分别相加

思路

最终公式     (n / y) * (y - k) + ((n % y< k) ?  0  :  (n % y - k + 1));

推导过程

（1）明确条件

正整数数对（x，y），由用户输入的控制条件 n、k

x、y均不大于n，且 x % y >= k

要求输出给定 n、k下，数对（x，y）的个数。

为了进一步熟悉题意，我们可以分析一下示例，如题干所给的例子：

n = 5，k = 2.

也就是说，要找到数对（x，y），其中x和y两数都不能比5大，而x%y不能比2小。

那么x和y都只能取：1、2、3、4、5，且要在其中枚举出x、y的值，一一搭配，找到 x%y 的值比2大的组合。模拟以上过程：先确定数对中的其中一个值，再将以上区间中的5个值一一代入另一个数，检查x%y是否符合条件。

现在的问题就转变成了：以谁为根据，对另一个数进行枚举？

2）先确定除数与余数的数学关系

分析x与y，x是被模数（或者说被除数），y是模数（或者说除数）。注意：y与余数是有数学关系的。

由于需要满足的条件是 x%y>=k，那么 y 的取值范围显然属于区间[k+1, n]，不可能小于或等于k。（y是除数，k是余数，余数不可能 >= 除数）。

比如某个数i， i % 2，结果一定在0、1中。若i除以一个数，余数 k = 3，则反推除数一定比3大。如：10 % 7 = 3；但 10 % 3，10 % 2，10 % 1分别为1，0，0，不可能等于3

因此，我们根据y的取值范围进行枚举，即：对于每一个y，来统计满足x%y>=k这一条件的数对个数；将所有的y对应的数对个数相加即可。

现在的问题又转变成了：对于某个特定的y，如何计算满足条件的数对的个数？

（3）确定余数周期

由于x属于[1,n]区间，且x按y模，我们可按y再将其划分为若干个小区间（t个小区间，每个区间长y）：

[1,     2,     ...,     y]

[y+1,   y+2,   ...,     2y]

[2y+1,  2y+2,  ...,     3y]

...

[ty+1,   ty+2,   ...,     n]

 ，表示把n共划分为t个长度为y的小区间。

由上不难发现，余数呈周期性变化，当除数为y时，余数周期性变化：1、2、… 、y-1、0，变化周期为y。

那么对于上述的t个小区间来说，每个小区间内满足x%y >= k 的被除数x有y-k个。举个例子：y = 5，k = 3，则一定存在如下区间：

x ∈ [1, 2, 3, 4, 5]

x % 5 >= 3,则只有4和5，也就是5 - 3即y - k个。

除了最后一个小区间，前面的小区间都为一个完整的余数变化周期。而最后一个不完整周期的余数变化是1 到 n%y，满足条件的个数是0个或n%y-k+1（因为区间不完整，所以可能有也可能没有，没有就是0个，有的话就是（n%y-k+1）个）。

（4）总结已知条件

1. 除数y的范围为：k+1 到 n。
2. 利用将x按y区间划分，得完整余数周期个数为n/y。
3. 每个完整周期内满足 x%y>=k 的被除数有y-k个。
4. 最后一个不完整周期是1 到 n%y，满足条件的元素个数是n%y-k+1或0，这取决于最后一项 n%y 是否小于 k。
5. 特殊判断：当k=0时，满足条件的x和y数对直接就有n*n个。

因此，总结出公式：

代码-1

#include <stdio.h>  int main() {     long n, k;     //本题中数值比较大，应用long来定义整数     while(~scanf("%ld %ld", &n, &k))    {         if (k == 0)     //单独判断k==0的情况        {             printf("%ld\n", n * n);    //任意数对的取模结果都是大于等于0的             continue;         }                long count = 0;         for(long y = k + 1; y <= n; y++)     //y的范围：k+1到n        {             //每种情况都加起来            count += ((n / y) * (y - k)) + ((n % y < k) ? 0 : (n % y - k + 1));         }         printf("%ld\n", count);     }     return 0; }

该方法的时间复杂度为O(n)，空间复杂度为O(1)。

代码-2

这是以上思路的另一种写法，将各个部分分开写了，而没有直接写成公式。

也许更为清晰。

#include<stdio.h> int main() {    int n, k;    while (~scanf("%d %d", &n, &k)) {        long count = 0;        if (0 == k || 1 == k) {            count = (long)n * n;            printf("%ld", count);            continue;        }                int x;        int y = k + 1;        while (y <= n) {             //共 n/y 个完整周期            int each_times = n / y;               //最后一个余数值            int last_num = n % y;                //所有完整周期下符合题干要求的元素个数            int all_times = each_times * (y - k);               //最后一个周期下可能符合题干要求的元素个数            int last_times = last_num - k + 1;            //判断最后一个余数值是否大于k            if (last_num < k) {                count += all_times;   //小于，则不考虑            } else {                count += (all_times + last_times);            }            y++;        }        printf("%ld\n", count);        return 0;    } }

三、总结

1. 对于我这样的数学渣来说，其实理解的过程还是有点痛苦的。我的观点在，需要熟悉数学方法分析数学相关的编程题的思维，倒不是说要非要记住这道题怎么解。

1. 数学方法很多时候能优化时间复杂度。最简单的例子求1到n的累加和，如果有等差数列公式，那么时间复杂度为O(1)，但for循环sum += i，则时间复杂度难免为O(N)了。是一个破解时间复杂度太高的一个利器。