結果

問題 No.3416 マッチ棒パズル Extra
コンテスト
ユーザー svel gr
提出日時 2026-01-05 14:44:31
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 3,025 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 850 ms
コンパイル使用メモリ 111,116 KB
実行使用メモリ 19,408 KB
最終ジャッジ日時 2026-01-05 14:44:41
合計ジャッジ時間 9,314 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

/**
 * @brief 高速入出力テンプレ
 */
struct FastIO {
    FastIO() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    }
    inline long long read() {
        long long x;
        if (!(cin >> x)) return -1;
        return x;
    }
    inline void print(long long x) { cout << x << "\n"; }
} io;

/**
 * @brief 自動で Mod を取る整数型
 */
template<int mod>
struct Mint {
    long long v;
    Mint(long long _v = 0) : v((_v % mod + mod) % mod) {}
    Mint operator+(const Mint& o) const { return Mint(v + o.v); }
    Mint operator-(const Mint& o) const { return Mint(v - o.v); }
    Mint operator*(const Mint& o) const { return Mint(v * o.v); }
    friend ostream& operator<<(ostream& os, const Mint& m) { return os << m.v; }
};
using modint = Mint<998244353>;

/**
 * @brief 格子点計数クラス
 * 2xy + x + y <= N (x, y >= 1) を満たす整数の組
 */
struct LatticeCounter {
    using i128 = __int128_t;

    // (2x+1)(2y+1) <= K を満たす x > y >= 1 の個数を SBT で求める
    modint count_points(long long n) {
        long long k = 2 * n + 1;
        long long border = (sqrt(k) - 1) / 2;
        while ((i128)(2 * border + 3) * (2 * border + 3) <= k) border++;
        while ((i128)(2 * border + 1) * (2 * border + 1) > k) border--;

        if (border < 1) return modint(0);

        long long x = border + 1;
        long long y = (k / (2 * x + 1) - 1) / 2;
        if (y < 0) y = 0;
        
        modint res = 0;
        long long limit_y = pow(k, 1.0 / 3.0);
        
        auto is_inside = [&](long long tx, long long ty) {
            return (i128)(2 * tx + 1) * (2 * ty + 1) <= k;
        };

        // Stern-Brocot Tree による境界追跡
        auto dfs = [&](auto self, long long dx1, long long dy1, long long dx2, long long dy2) -> void {
            while (is_inside(x + dx1, y - dy1)) {
                if (y <= dy1) break;
                res = res + modint(x - border) * dy1 + modint(dy1) * (dx1 - 1) * 499122177; // 499122177 は 2 の逆数
                x += dx1; y -= dy1;
            }
            if (y <= limit_y) return;

            long long mx = dx1 + dx2, my = dy1 + dy2;
            if (is_inside(x + mx, y - my)) {
                self(self, mx, my, dx2, dy2);
            } else {
                if ((i128)(2 * y + 1) * mx <= (i128)(2 * x + 1) * my) return;
                self(self, dx1, dy1, mx, my);
            }
        };

        dfs(dfs, 1, 0, 0, 1);

        for (long long i = 1; i <= y; ++i) {
            long long cur_x = (k / (2 * i + 1) - 1) / 2;
            if (cur_x > border) res = res + modint(cur_x - border);
        }

        return res * 2 + modint(border);
    }
};

void solve() {
    long long n = io.read();
    if (n < 0) return;
    
    LatticeCounter lc;
    io.print(lc.count_points(n).v);
}

int main() {
    int t = io.read();
    while (t-- > 0) {
        solve();
    }
    return 0;
}
0