#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
const ll w=100000;

int main() {
    int tc;
    scanf("%d",&tc);
    while(tc--) {
        ll n,m;
        scanf("%lld%lld",&n,&m);
        ll max=w*w*10;
        ll min=-max;
        while(min<max) {
            ll x = (min+max)/2;
            if(x==max) x--;
            ll sum = 0;
            for(ll j = 1; j <= n && sum<=m; ++j) {
                ll det = (w+j)*(w+j) - 4*(j*j-w*j-x);
                if(det>=0) {
					ll q = int(sqrt(det));
					if((q+1)*(q+1) <= det) q++;
                    ll x0 = (-(w+j)-q)/2;
                    ll x1 = (-(w+j)+q)/2;
                    if(x0<1) x0=1;
                    if(x1>n) x1=n;
                    if(x0<=x1) sum+=(x1-x0+1);
                }
            }
            if(sum<m) min=x+1;
            else max=x;
        }
        printf("%lld\n",min);
    }
    return 0;
}



以下是int64
#include <iostream>
#include <cmath>
#define ll __int64
using namespace std;
const ll w=100000;

int main() {
    int tc;
    scanf("%d",&tc);
    while(tc--) {
        ll n,m;
        scanf("%I64d%I64d",&n,&m);
        ll max=w*w*10;
        ll min=-max;
        while(min<max) {
            ll x = (min+max)/2;
            if(x==max) x--;
            ll sum = 0;
            for(ll j = 1; j <= n && sum<=m; ++j) {
                ll det = (w+j)*(w+j) - 4*(j*j-w*j-x);
                if(det>=0) {
					ll q = int(sqrt(det));
					if((q+1)*(q+1) <= det) q++;
                    ll x0 = (-(w+j)-q)/2;
                    ll x1 = (-(w+j)+q)/2;
                    if(x0<1) x0=1;
                    if(x1>n) x1=n;
                    if(x0<=x1) sum+=(x1-x0+1);
                }
            }
            if(sum<m) min=x+1;
            else max=x;
        }
        printf("%I64d\n",min);
    }
    return 0;
}

• Windows 版 g++ 里， long long 要用 scanf("%I64d")、printf("%I64d")。 (0) ImLazy 2008-09-16 16:24:54