Submission #3225659

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll a, b;
int q;

ll imax(ll X){
    ll lo = 1, mi, hi = sqrt(X) + 2;
    while(lo < hi){
        mi = (lo + hi + 1) >> 1;
        if(mi * (mi - 1) < X) lo = mi;
        else hi = mi - 1;
    }
    return lo;
}

const int lim = 5;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(cin >> q; q--; ){
        cin >> a >> b;
        if(a == 1 && b == 1){
            cout << 0 <<'\n';
            continue;
        }
        ll ansa = 0, ansb = 0;
        ll k = imax(a*b-1);
        if(a > 1){
            if(a < lim){
                set<ll> S;
                for(int j = 1; j < a; j++) if((a*b-1)/j > b) S.insert((a*b-1)/j);
                ansa += S.size();
                S.clear();
            }else{
                if(k >= (a*b-1)) ansa += (a*b-1) - b;
                else if(k <= b){
                    ansa += (a*b-1)/(b+1);
                }else{
                    ansa += k - b + max(0LL, (a*b-1)/k - 1);
                    //printf("ans1 : %lld\n",k + max(0LL, (a*b-1)/k - (a*b-1)/(a+1)));
                }
            }
        }
        if(b > 1){
            if(b < lim){
                set<ll> S;
                for(int j = 1; j < b; j++) if((a*b-1)/j > a) S.insert((a*b-1)/j);
                ansb += S.size();
                S.clear();
            }else{
                if(k >= (a*b-1)) ansb += (a*b-1) - a;
                else if(k < a){
                    ansb += (a*b-1)/(a+1);
                }else{
                    ansb += k - a + max(0LL, (a*b-1)/k - 1);
                    //printf("ans1 : %lld\n",k + max(0LL, (a*b-1)/k - (a*b-1)/(a+1)));
                }
            }
        }
        //printf("a = %lld, b = %lld, k = %lld\n",a,b,k);
        //printf("ansa = %lld, ansb = %lld\n",ansa,ansb);
        cout << ansa + ansb << '\n';
    }
}

Submission Info

Judge Result