結果

問題 No.2066 Simple Math !
ユーザー 👑 NachiaNachia
提出日時 2022-09-02 23:39:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 178 ms / 2,000 ms
コード長 2,722 bytes
コンパイル時間 701 ms
コンパイル使用メモリ 77,552 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-27 23:12:52
合計ジャッジ時間 5,298 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 6 ms
6,940 KB
testcase_02 AC 14 ms
6,944 KB
testcase_03 AC 5 ms
6,940 KB
testcase_04 AC 173 ms
6,940 KB
testcase_05 AC 173 ms
6,940 KB
testcase_06 AC 169 ms
6,940 KB
testcase_07 AC 169 ms
6,940 KB
testcase_08 AC 170 ms
6,944 KB
testcase_09 AC 174 ms
6,940 KB
testcase_10 AC 174 ms
6,944 KB
testcase_11 AC 174 ms
6,940 KB
testcase_12 AC 171 ms
6,940 KB
testcase_13 AC 175 ms
6,944 KB
testcase_14 AC 178 ms
6,944 KB
testcase_15 AC 166 ms
6,944 KB
testcase_16 AC 168 ms
6,940 KB
testcase_17 AC 162 ms
6,940 KB
testcase_18 AC 163 ms
6,944 KB
testcase_19 AC 55 ms
6,944 KB
testcase_20 AC 55 ms
6,940 KB
testcase_21 AC 54 ms
6,944 KB
testcase_22 AC 54 ms
6,940 KB
testcase_23 AC 55 ms
6,944 KB
testcase_24 AC 89 ms
6,940 KB
testcase_25 AC 89 ms
6,940 KB
testcase_26 AC 87 ms
6,940 KB
testcase_27 AC 87 ms
6,944 KB
testcase_28 AC 87 ms
6,940 KB
testcase_29 AC 30 ms
6,940 KB
testcase_30 AC 6 ms
6,940 KB
testcase_31 AC 10 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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;
        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(r == P*Q) r = P*Q + (K-f(P*Q)) + 1;
        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