Submission #3225837


Source Code Expand

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

typedef long long ll;
const int lim = 5;
ll a, b;
int q;

ll imax(ll X){
    ll lo = 1, mi, hi = 2e9;
    while(lo < hi){
        mi = (lo + hi + 1) >> 1;
        if(mi * (mi - 1) < X) lo = mi;
        else hi = mi - 1;
    }
    return lo;
}
ll mysol(ll a, ll b){
        if(a == 1 && b == 1){
            return 0;
        }
        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);
        //return ansa + ansb + min(a-1-ansa,b-1-ansb);
        return ansa + ansb;
}

ll sol2(ll a, ll b){
    if(a > b) swap(a,b);
    if(b <= a + 1) return a + a - 2;
    ll lo = 0, mi, hi = 2e9;
    while(lo < hi){
        mi = (lo + hi + 1) >>1;
        if(mi * mi < a * b) lo = mi;
        else hi = mi - 1;
    }
    ll c = lo;
    return c*(c+1) < a*b ? c + c - 1 : c + c - 2;
}

mt19937 g(0x95949);
uniform_int_distribution<int> d(1,1e9);

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(cin >> q; q--; ){
        cin >> a >> b;
        //a = d(g); b = a + 1;
        //if(mysol(a,b) == sol2(a,b)) continue;
        //cout << "mysol = " << mysol(a,b) << '\n';
        cout << mysol(a,b) << '\n';
    }
}

Submission Info

Submission Time
Task D - Worst Case
User TAMREF
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2516 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 1
AC × 7
WA × 5
Set Name Test Cases
Sample s1.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, s1.txt
Case Name Status Exec Time Memory
01.txt WA 1 ms 256 KB
02.txt AC 1 ms 256 KB
03.txt AC 1 ms 256 KB
04.txt AC 1 ms 256 KB
05.txt AC 1 ms 256 KB
06.txt AC 1 ms 256 KB
07.txt WA 1 ms 256 KB
08.txt WA 1 ms 256 KB
09.txt WA 1 ms 256 KB
10.txt WA 1 ms 256 KB
11.txt AC 1 ms 256 KB
s1.txt AC 1 ms 256 KB