给定n,m,min和max，求所有的<i,j>，满足0<=i<=n,0<=j<=m并且min<=i*j<=max。

要求：不得使用暴力法，算法复杂度要求O(n,m)<nlogm并且O(n,m)<mlogn。

提示：

1.设有k和l，若满足k*l<min，对于i<=k且j<=l，则<i,j>是不满足条件的；若k*l>max，对于i>=k且j>=l，则<i,j>是不满足条件的。

2.可以考虑用三分法。

3.需要考虑n和m比较小的情形，例如0,1,2，也许需要做特殊的处理。

样例数据如下：

输入：n,m,min和max分别为10,10,31,41

结果：

<4 8>

<4 9>

<4 10>

<5 7>

<5 8>

<6 6>

<7 5>

<8 4>

<8 5>

<9 4>

<10 4>

暴力法程序如下：

/* B00015 平方矩阵问题（暴力法） */#include 
    
     using namespace std;int main(){    int n, m, mins, maxs;　scanf("%d%d%d%d", &n, &m, &mins, &maxs);    for(int i=0; i<=n; i++)        for(int j=0; j<=m; j++) {            if(mins <= i * j && i * j <= maxs)                printf("<%d %d>\n", i, j);        }    return 0;}
    

运行结果（输入与输出）：

10 10 31 41<4 8><4 9><4 10><5 7><5 8><6 6><7 5><8 4><8 5><9 4><10 4>

根据网友提供的程序改进后的程序：

/* B00015 平方矩阵问题（二分法） */#include 
    
     #include 
     
      using namespace std;int b_search_max(int row, int left, int right , int maxs){    int mid;    while(left <= right) {        mid = (left + right) / 2;        if(row * mid > maxs)            right = mid - 1;        else if(row * mid < maxs)            left = mid + 1;        else { // ==            left = mid;            break;        }    }    return right;}int b_search_min(int row, int left, int right , int mins){    int mid;    while(left <= right) {        mid = (left + right) / 2;        if(row * mid < mins)            left = mid + 1;        else if(row * mid > mins)            right = mid - 1;        else { // ==            left = mid;            break;        }    }    return left;}int main(){    int n, m, mins, maxs;    int bot, top;    scanf("%d%d%d%d", &n, &m, &mins, &maxs);    for(int i=0; i<=n; i++) {        top = b_search_max(i, 0, m, maxs);        bot = b_search_min(i, 0, top, mins);        for(int j = bot; j <= top; j++)            printf("<%d %d>\n", i, j);    }    return 0;}
     
    

运行结果（输入与输出）之一：

10 10 31 41<4 8><4 9><4 10><5 7><5 8><6 6><7 5><8 4><8 5><9 4><10 4>

运行结果（输入与输出）之二：

15 15 31 41<3 11><3 12><3 13><4 8><4 9><4 10><5 7><5 8><6 6><7 5><8 4><8 5><9 4><10 4><11 3><12 3><13 3>

进一步改进后的程序：

/* B00015 平方矩阵问题（综合二分法） */#include 
    
     #include 
     
      using namespace std;int b_search_max(int row, int left, int right , int maxs){    int mid;    while(left <= right) {        mid = (left + right) / 2;        if(row * mid > maxs)            right = mid - 1;        else if(row * mid < maxs)            left = mid + 1;        else { // ==            left = mid;            break;        }    }    return right;}int b_search_min(int row, int left, int right , int mins){    int mid;    while(left <= right) {        mid = (left + right) / 2;        if(row * mid < mins)            left = mid + 1;        else if(row * mid > mins)            right = mid - 1;        else { // ==            left = mid;            break;        }    }    return left;}int main(){    int n, m, mins, maxs;    int bot, top;    scanf("%d%d%d%d", &n, &m, &mins, &maxs);    int minrow = b_search_min(m, 0, n, mins);    int maxcol = b_search_max(minrow, 0, m, maxs);    int mincol = b_search_min(n, 0, maxcol, mins);    int maxrow = b_search_max(mincol, minrow, n, maxs);    for(int i=minrow; i<=maxrow; i++) {        top = b_search_max(i, mincol, maxcol, maxs);        bot = b_search_min(i, mincol, top, mins);        for(int j = bot; j <= top; j++)            printf("<%d %d>\n", i, j);    }    return 0;}
     
    

运行结果（输入与输出）之一：

10 10 31 41<4 8><4 9><4 10><5 7><5 8><6 6><7 5><8 4><8 5><9 4><10 4>

运行结果（输入与输出）之二：

15 15 31 41<3 11><3 12><3 13><4 8><4 9><4 10><5 7><5 8><6 6><7 5><8 4><8 5><9 4><10 4><11 3><12 3><13 3>