結果

問題 No.1918 Simple Math ?
コンテスト
ユーザー Vladimir Novikov
提出日時 2025-10-01 22:01:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,957 bytes
コンパイル時間 1,957 ms
コンパイル使用メモリ 202,304 KB
実行使用メモリ 10,916 KB
最終ジャッジ日時 2025-10-01 22:01:08
合計ジャッジ時間 6,996 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define len(a) (int)((a).size())

const ll INF = 1'000'000'000'000'000'000, MOD = 1'000'000'007;

ll root(ll a) {
    ll v = sqrt(a);
    while (v * v > a) --v;
    while ((v + 1) * (v + 1) <= a) ++v;
    return v;
}

ll solve(ll a, ll n) {
    if (true) {
        ll ans = 0, pr_i = -1, calc = 0, cur = 1;
        auto get_i = [&](ll cur){
            ll val = cur * cur;
            ll i = (val + (a - 1)) / a;
            return i;
        };
        while (true) {
            ll i = get_i(cur);
            if (i > n) break;

            ll nxt_cur = cur;
            ll l = cur, r = MOD;
            while (r - l > 1) {
                ll mid = (l + r) / 2;
                if (get_i(mid) == get_i(cur)) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            ans += (n - i + 1) * (r - cur);
            ans %= MOD;
            cur = r;
        }
        //cout << calc << endl;
        return ans;
    }
    struct q {
        ll a, add, n;
    };
    vector<q> vec = { {a, 0, n} };
    for (int i = 0; i < 16; ++i) {
        vector<q> nw;
        for (auto c : vec) {
            if (c.n / 2 > 0) nw.push_back({c.a * 2, c.add, c.n / 2});
            nw.push_back({c.a * 2, c.add - c.a, (c.n + 1) / 2});
            assert((c.n + 1) / 2 > 0);
        }
        vec = nw;
    }

    ll flr = INF, cel = -1;
    for (auto c : vec) {
        flr = min(flr, c.n);
        cel = max(cel, c.n);
    }
    assert(cel - flr <= 1);
    if (cel == flr) ++cel;

    ll ans = 0;
    for (auto curn : {flr, cel}) {
        ll sum = 0;
        vector<ll> vals(curn + 1);
        priority_queue<pair<ll, ll>> next_upd;
        ll mul = vec[0].a;
        for (ll i = 1; i <= curn; ++i) {
            ll rt = root(i * mul);
            vals[i] = rt;
            sum += rt;
            if (sum >= MOD) sum -= MOD;
            next_upd.push({rt * rt - 1 - i * mul, i});
        }
        vector<ll> adds;
        ll cur_add = 0;
        for (auto v : vec) {
            if (v.n == curn) adds.push_back(v.add);
        }
        next_upd.push({-INF, n});
        sort(rall(adds));
        for (auto c : adds) {
            auto v = next_upd.top();
            while (v.first >= c) {
                next_upd.pop();
                sum -= 1;
                if (sum < 0) sum += MOD;
                vals[v.second]--;
                next_upd.push({vals[v.second] * vals[v.second] - 1 - v.second * mul, v.second});
                v = next_upd.top();
            }

            ans += sum;
            ans %= MOD;
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        ll a, n;
        cin >> a >> n;
        cout << solve(a, n) << endl;
    }

    return 0;
}
0