题目

时间复杂度要求是 $O(n)$

我只有 $O(n^2)$

代码如下：

#include<bits/stdc++.h>
typedef unsigned long long ll;
using namespace std;
ll t,n,m,ans;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        ans=0;
        for(ll a=n;a<=m;a++)
            for(ll b=a+1;b<=m;b++){
                ll c=ll(sqrt(a*a+b*b));
                if(c*c==a*a+b*b && c<=m ) {
                    ans++;
                }
            }
        printf("%lld\n",ans);
    }
    return 0;
}