結果

問題 No.3416 マッチ棒パズル Extra
コンテスト
ユーザー Kude
提出日時 2025-12-23 23:26:22
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 5,521 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,041 ms
コンパイル使用メモリ 370,948 KB
実行使用メモリ 19,408 KB
最終ジャッジ日時 2025-12-23 23:26:35
合計ジャッジ時間 12,809 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
using u256 = boost::multiprecision::uint256_t;
// using u128 = boost::multiprecision::uint128_t;
using u128 = uint128_t;
// using ull = boost::multiprecision::number<cpp_int_backend<64, 64, unsigned_magnitude, unchecked, void> >;
using ull = unsigned long long;
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;

// https://259-momone.hatenablog.com/entry/2021/07/25/025655
#include<iostream>
#include<vector>
#include<tuple>
#include<cmath>

using namespace std;

template<typename Integer, typename Result = Integer>
constexpr Result sqrt_floor(const Integer& n){
    if(n <= 1)return n;
    Integer r(sqrt(n));
    do r = (r & n / r) + (r ^ n / r) / 2; while(r > n / r);
    return r;
}
template<typename Integer>
constexpr bool is_inside(const Integer& x, const Integer& y, const Integer& n){
  // (2x+1)(2y+1) >= 2n
  using ull0 = unsigned long long;
  ull0 z;
  if (__builtin_mul_overflow(ull0(2*x+1), ull0(2*y+1), &z)) return true;
  return z >= 2*n;
}
template<typename Integer>
constexpr bool is_cross(const Integer& x, const Integer& y, const Integer& a, const Integer& b, const Integer& n){
    // if(a == 0 || b == 0)return a * y > b * x;
    // (x+1/2)(y+1/2) >= n/2
    assert(a > 0);
    if (b == 0) {
        // y > -1/2
        return y >= 0;
    }

    // (b(2x+1)+a(2y+1))^2 <= 8abn
    auto lhs = u128(b) * (2 * x + 1) + u128(a) * (2 * y + 1);
    auto rhs = u256(8 * b) * (u128(a) * n);
    auto lhs2 = u256(lhs) * lhs;
    if (lhs2 < rhs) return false;
    return u128(a) * (2 * y + 1) > u128(b) * (2 * x + 1);
}
constexpr ull next_in(const ull& x, const ull& y, const ull& a, const ull& b, const ull& n){
    assert(a > 0);
    if (b == 0) {
        assert(a == 1);
        // ceil((2n-2y-1)/(4y+2)) - x
        return (n + y) / (2 * y + 1) - x;
    }
    // if(b == 0)return (n - x * y + a * y - 1) / (a * y);
    
    auto lhs = u128(b) * (2 * x + 1) + u128(a) * (2 * y + 1);
    auto rhs = u256(8 * b) * (u128(a) * n);
    auto D = u256(lhs) * lhs - rhs;
    using namespace std;
    
    auto denom = 4 * a * u128(b);
    assert(denom > 0);
    auto res = (a * u128(2 * y + 1) + denom - 1 - b * u128(2 * x + 1) - boost::multiprecision::sqrt(D)) / denom;
    return (ull)(res);
    // return (a * y - sqrt_floor<__uint128_t, ull>(static_cast<__uint128_t>(b * x + a * y) * (b * x + a * y) - static_cast<__uint128_t>(4) * a * b * n) - b * x + 2 * a * b - 1) / (2 * a * b);
}
constexpr ull next_out(const ull& x, const ull& y, const ull& a, const ull& b, const ull& n){
    assert(b > 0);
    if (a == 0) {
        assert(b == 1);
        return y - (n + x) / (2 * x + 1);
    }
    // if(a == 0)return (x * y - n) / (x * b);
    auto lhs = u128(b) * (2 * x + 1) + u128(a) * (2 * y + 1);
    auto rhs = u256(8 * b) * (u128(a) * n);
    auto D = u256(lhs) * lhs - rhs;
    auto denom = 4 * a * u128(b);
    assert(denom > 0);
    auto res = (a * u128(2 * y + 1) + boost::multiprecision::sqrt(D) - b * u128(2 * x + 1)) / denom;
    return (ull)(res);
}

template<typename Integer>
mint count_divisors(const Integer& X){
    using namespace std;
    using integer_type = Integer;

    using subtree_type = std::tuple<integer_type, integer_type, integer_type, integer_type>;
    vector<subtree_type> stern_brocot_tree{{1, 0, 0, 1}, {0, 1, 0, 0}};

    using point_type = std::pair<integer_type, integer_type>;
    auto LMT = (2*X-3+5)/6;
    auto V = ((unsigned long long)sqrtl((unsigned long long)(2*X))-1)/2;
    point_type now_point{V+1, (-2*V+2*X-3+4*V+5)/(4*V+6)};


    mint result{int((now_point.second - 1) % mint::mod())};

    while(now_point.first <= LMT){
        auto& [x, y]{now_point};

        // subtree between a/b and c/d
        auto [a, b, c, d]{stern_brocot_tree.back()};
        stern_brocot_tree.pop_back();

        if(b == 0)break;

        // next vertex of convex hull
        const auto n_upper{next_out(x, y, a, b, X)};
        result += mint::raw(int((u128(a * n_upper) * y - (u128(a * n_upper + 1) * (b * n_upper + 1) + n_upper) / 2) % mint::mod()));
        x += n_upper * a;
        y -= n_upper * b;

        // backtrack
        while(!empty(stern_brocot_tree)){
            tie(a, b, c, d) = stern_brocot_tree.back();
            if(is_inside(x + a, y - b, X))break;
            stern_brocot_tree.pop_back();
        }

        if(empty(stern_brocot_tree))break;

        // search forward
        while(y > d){
            if(y > b + d && is_inside(x + a + c, y - b - d, X)){
                const auto n_lower{next_out(x + a + c, y - b - d, c, d, X)};
                tie(a, b, c, d) = make_tuple(a + c * (n_lower + 1), b + d * (n_lower + 1), a + c * (n_lower + 2), b + d * (n_lower + 2));
            }else if(is_cross(x + c, y - d, a, b, X)){
                const auto n_lower{next_in(x + c, y - d, a, b, X)};
                if(y < b * n_lower + d || !is_inside(x + a * n_lower + c, y - b * n_lower - d, X)) break;
                tie(a, b, c, d) = make_tuple(a * n_lower + c, b * n_lower + d, a * (n_lower - 1) + c, b * (n_lower - 1) + d);
            }else break;
            stern_brocot_tree.emplace_back(a, b, c, d);
        }
    }

    return 2 * result + mint(V).pow(2);
}

int main(){
    using namespace std;
    using integer_type = ull;
    int tt;
    cin >> tt;
    while (tt--) {
      integer_type N;
    //   unsigned long long N;
      cin >> N;
      auto ans = count_divisors(N + 1);
      cout << ans.val() << '\n';
    }
}
0