結果

問題 No.2066 Simple Math !
コンテスト
ユーザー Nachia
提出日時 2022-09-02 23:36:30
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,720 bytes
コンパイル時間 2,212 ms
コンパイル使用メモリ 103,392 KB
最終ジャッジ日時 2025-02-07 01:57:39
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Main.cpp"

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#line 2 "nachia\\math\\floor-sum.hpp"

#include <cassert>
#include <utility>

namespace nachia{


// a : any value
// mod != 0
std::pair<long long, unsigned long long> SafeDiv(long long a, unsigned long long mod){
    using u64 = unsigned long long;
    if(a >= 0) return std::make_pair(0, (u64)a);
    if(mod >= (u64)1 << 62) return std::make_pair(-1, (u64)a + mod);
    long long q = a / mod;
    long long m = a % (long long)mod;
    if(m){ q--; m += mod; }
    return std::make_pair(q, m);
}

unsigned long long nC2Uint64(unsigned long long n){
    return (n%2) ? ((n-1)/2*n) : (n/2*(n-1));
}

// n : any
// 1 <= m
// a : any
// b : any
// n * a%m + b%m < 2**64
unsigned long long FloorSumU64Unsigned(
    unsigned long long n,
    unsigned long long m,
    unsigned long long a,
    unsigned long long b
){
    using u64 = unsigned long long;
    assert(1 <= m);
    u64 ans = 0;
    while(n){
        if(a >= m){
            ans += a / m * nC2Uint64(n);
            a %= m;
        }
        if(b >= m){
            ans += b / m * n;
            b %= m;
        }
        u64 y_max = a * n + b;
        if (y_max < m) return ans;
        n = y_max / m;
        b = y_max % m;
        y_max = a; a = m; m = y_max;
    }
    return ans;
}

// n : any
// 1 <= m
// a : any
// b : any
// (n+1) * m < 2**64
unsigned long long FloorSumU64Signed(
    unsigned long long n,
    unsigned long long m,
    long long a,
    long long b
){

    using u64 = unsigned long long;
    auto ua = SafeDiv(a, m);
    auto ub = SafeDiv(b, m);
    u64 ans = FloorSumU64Unsigned(n, m, ua.second, ub.second);
    ans += ua.first / m * nC2Uint64(n);
    ans += ub.first / m * n;
    return ans;
}

} // namespace nachia
#line 8 "Main.cpp"

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

u64 GCD(u64 a, u64 b){
    if(b == 0) return a;
    return GCD(b, a%b);
}

int main(){
    int T; cin >> T;
    rep(i,T){
        u64 P,Q,K; cin >> P >> Q >> K;
        u64 g = GCD(P,Q); P /= g; Q /= g;
        if(P > Q) swap(P,Q);
        u64 l = 0, r = P*Q+1;
        auto f = [&](u64 N) -> u64 {
            return nachia::FloorSumU64Unsigned(N/P+1, Q, P, N%P) + (N/P);
        };
        while(l + 1 < r){
            u64 N = (l+r)/2;
            if(f(N) < K) l = N; else r = N;
        }
        if(l == P*Q) r = P*Q + (K-f(P*Q));
        cout << r*g << '\n';
    }
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0