原题大意

给出两个整数n和m，请统计满足0＜a＜b＜n并且使得 (a2+b2+m)/(ab) 的结果是整数的整数对(a,b)的个数。

本题包含多组测试例。当测试例数据是n=m=0时，表示输入结束。（测试例数量<6000）
每个测试例一行，是两个整数n和m。输入保证0≤n≤1000，-20000 < m < 20000。

算法分析

case=1的时候很容易可以想到一个n^2的暴力
那么在case比较大的时候，把所有case根据n的数值进行排序。再离线处理，枚举每一组(a,b)，穷举整数t∈[-20000,20000]，当符合条件(a^2+b^2+t)%ab==0时，ans[t]++，最后根据case的顺序从离线处理中获取答案，复杂度O(∑(i=1..n,j=2..n) (40000/ab)) + O(n^1.5)

程序代码

#include <bits/stdc++.h>
using namespace std;
int n[10100], m[10100];
int ret[10100];
vector<int> id[40404];
int main(){
    int i = 0;
    while(scanf("%d%d",&n[i],&m[i]) != EOF && (n[i] || m[i])){
        id[m[i]+20000].push_back(i);
        i++;
    }
    for(int a = 1; a <=1000; a++){
        for(int b = a+1; b <= 1000; b++){
            int M = a*b-(a*a+b*b)%(a*b);//M的功能类似矫正参数
            for(int t = 0; M + t *(a*b)<= 20000;t++){
                for(int i = 0; i < id[M+t*(a*b)+20000].size(); i++)
                {
                    if(b < n[id[M+t*(a*b)+20000][i]]) ret[id[M+t*(a*b)+20000][i]]++;
                }
            }
            for(int t = 1; M - t*(a*b) >= -20000; t++)
                for(int i = 0; i < id[M-t*(a*b)+20000].size(); i++)
                {
                    if(b < n[id[M-t*(a*b)+20000][i]]) ret[id[M-t*(a*b)+20000][i]]++;
                }
        }
    }   
    for(int i = 0;n[i]||m[i];i++)
        printf("Case %d: %d\n",i+1, ret[i]);
    return 0;
}