計算量のlogCの出どころを知りたい。

Question

前提

下記に示すプログラムの計算量を知りたいです。
解答では、（NlogNlogC）となっています。
NlogNまでは、二分探索とソートの処理というめぼしはつくのですが、logCの行方がわからず困っております。

該当のソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    long long N, K;
    cin >> N >> K;
    vector<long long> a(N), b(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) cin >> b[i];

    // b はあらかじめソートしておく
    sort(b.begin(), b.end());

    // 判定問題
    auto check = [&](long long x) -> bool {
        long long cnt = 0;
        for (int i = 0; i < N; ++i) {
            cnt += upper_bound(b.begin(), b.end(), x / a[i]) - b.begin();
        }
        return (cnt >= K);
    };

    // 二分探索 (right は十分大きな値に設定)
    long long left = 0, right = 1LL<<60;
    while (right - left > 1) {
        long long mid = (left + right) / 2;
        if (check(mid)) right = mid;
        else left = mid;
    }
    cout << right << endl;
}

試したこと

再度ひとつずつ、計算量を見てみるも、N、logNしか見当たらずでした。

補足情報（FW/ツールのバージョンなど）

解説には最大値とありますが、そもそもプログラム内にmax関数なんて使っていないような気がしています...
参考にした解説ページ
リンクに飛べます。

Answer 1

checkにNlogNかかるのはループ構造から自明とおもいます。
問題は外側のwhileが何回回るかで、このプログラム例ではrightの初期値は1<<60なので60回なわけですが、これがlogCに相当します。
というのもrightはmax(a)×max(b)が上限だからです。実際の値から求めてもいいですが、a,bの最大は1e9である前提なので2^30(1.07e9)で近似して2^60が出てくるわけです。

Answer 2

あまく詳しくないので，間違っているかもしれませんが，
logCは比較処理，具体的にプログラムの中では「if check(mid)...」の回数に関係するものだと思います。
値の比較処理自体，乗除加算と同様に演算時間がかかります。